문제 설명
•
사다리꼴 모양과 추가된 정삼각형을 정삼각형 타일과 마름모 타일로 빈틈없이 채우는 경우의 수를 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 브루트 포스 - 또는
풀이2 그리디
풀이3 DP - 상한
풀이 코드
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
복사