내 풀이
N = int(input())
MOD = 15746
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
for i in range(5, 1000001):
dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])유사한 dp문제들을 많이 풀어봤길래 쉽게 풀었다. 하지만 dp 문제를 오랜만에 풀어서 그런지 정확한 근거를 충분히 세우지 못해 찾아봤다.
해설
먼저 길이가 i인 수를 만든다고 생각해보자. 그러면 사용할 수 있는 숫자 카드는 00과 1이다. 즉, 이전에 만든 수에다가 00을 붙이거나, 1을 붙여서 만든다는 얘기가 된다. 그런데 잘 생각해보면 00은 길이가 2이기 때문에 i-1번째에서는 붙일 수가 없다. 따라서 i-2번째에서 00을 붙여 만드는 경우와 i-1번째에서 1을 붙여 만들 수 있는 경우의 합이다.그런데 여기서 질문을 제기할 수 도 있다. 왜 i-2번째에서 1을 2개 붙여 만드는 경우는 생각하지 않는가?
그 이유는 바로 i-1번째에서 1을 붙여 만드는 경우와 중복되기 때문에다. N=5를 만드는 간단한 실험을 해보자
N=3인 경우 -> 001,100,111이고
N=4인 경우 -> 0011, 0000, 1001, 1100, 1111먼저 N-2인 경우(N=3)의 수들에 00을 붙여 나올 수 있는 수는 00001,00100, 10000,00111,11100이고, 1 두개를 붙여 만들 수 있는 수는 11001,10011,11111으로 전부 8개가 된다.
이번엔 N-1인 경우(N=4)의 수들에 1을 붙여 만들 수 있는 수를 구해보면 10011,00111,10000,00001,11001,11100,11111으로 총 7개가 된다.
근데 여기서 이미 눈치챘다시피 중복되는 숫자들이 상당히 있다. 여기서 중복들을 모두 제거해 보면 진짜 값은 8개가 된다. 그러나 이 수들을 모두 고려하여 중복을 제거하기란 여간 힘든일이 아니다.
따라서 N-2에선 00만 붙이고, N-1에선 1만 붙여 만든다고 정해보자. 그리고 수를 붙여줄 때 N-2의 경우의 수들엔 "맨 뒤에" 00을 붙이고, N-1의 경우의 수들엔 "맨 앞에" 1을 붙이는 규칙으로 만들어 보자
N-2의 맨 뒤에 00추가 -> 00100,10000,11100
N-1의 맨 앞에 1 추가-> 10011,10000,11001,1100,11111
이렇게 총 8개로 자연스럽게 중복이 제거되면서 값이 나오는 걸 볼 수 있다.
[출처][백준] 1904 - 01타일|작성자 occidere
