[BOJ] #1904 - 01타일

1904번: 01타일

 

 

** 문제 유형

• 동적 프로그래밍

 

** 풀이

1. 사용할 수 있는 타일의 종류는 2개: (1), (00)
2. 두 가지 종류의 타일을 이용하여, N 길이의 수열을 만드는 모든 경우의 수를 계산
3. 가장 전형적인 동적 프로그래밍 문제
4. N이 최대 1,000,000 이므로 시간 복잡도 O(N)으로 해결해야 함

 

+) 과정

• N = 2일 때, 경우의 수는 2가지 -> (11), (00)
• N = 3일 때, 경우의 수는 3가지

• N = 4일 때, 경우의 수는 5가지

 

• 동적 프로그래밍 문제를 풀기 위해서는 점화식(인접한 항들 사이의 관계식)을 세워야 함
• D[i] = '수열의 길이가 i일 때의 경우의 수' 라고 하면,
• D[i] = D[i - 1] + D[i - 2]
• cf) 피보나치 수열

 

n = int(input())

dp = [0] * 1000001 # 메모이제이션
dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i - 2] + dp[i - 1]) % 15746

print(dp[n])