Search

PGS 산 모양 타일링

생성일
2024/11/22 02:30
태그
다이나믹 프로그래밍

문제 설명

•
사다리꼴 모양과 추가된 정삼각형을 정삼각형 타일과 마름모 타일로 빈틈없이 채우는 경우의 수를 10007로 나눈 나머지를 구하는 문제

예제 입력/출력

n
tops
result
4
[1, 1, 0, 1]
149
2
[0, 1]
11
10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
7704

제약 조건

•
1≤n≤100,0001 ≤ n ≤ 100,000

문제 풀이

풀이1 브루트 포스 - O(2n)O(2^n) 또는 O(3n)O(3^n)
풀이2 그리디
풀이3 DP - 상한 O(n)O(n)

풀이 코드

def solution(n, tops): tops = [0] + tops dp = [0] * (n + 1) sub_dp = [0] * (n + 1) dp[0] = sub_dp[0] = 1 for i in range(1, n + 1): # sub_dp if tops[i] == 0: # 위에 없는 경우 sub_dp[i] = (dp[i - 1] + sub_dp[i - 1]) % 10007 if tops[i] == 1: # 위에 있는 경우 sub_dp[i] = (dp[i - 1] * 2 + sub_dp[i - 1]) % 10007 # dp dp[i] = (sub_dp[i] + dp[i - 1]) % 10007 return dp[n]
Python
복사

참고 자료