x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 2 for i in range(3, x + 1): d[i] = (d[i-1] + d[i-2]) % 15746 print(d[x]) 다이나믹 프로그래밍 문제이다. 점화식만 찾으면 아주 간단하게 해결할 수 있다. 계산값을 저장해둘 DP테이블(리스트 d)를 생성하고, 초기값을 넣어준다. d[1]엔 1길이의 수열에서 나올 수 있는 경우의 수의 개수, d[2]엔 2길이, d[x]엔 x길이의 수열에서 나올 수 있는 경우의 수의 개수가 들어간다. 타일 경우의 수를 구하는 것은 언뜻 답이 없어 보이지만, 규칙이 있다. 현재 값들에 1을 붙이고, 이전 값들에 00을 붙이면 그게 다음 값이 된다. 즉 N=4 일 때의 경우의 수를 구..