01 (1) 썸네일형 리스트형 [BOJ][DP] 1904. 01타일 문제 -> https://www.acmicpc.net/problem/1904 N이 홀수일 때, N이 짝수일 때 어떤 경우가 나올지 잘 생각해보면 금방 답이 도출이 된다.. 아래 그림을 보자. 먼저 N=0일 때, 타일을 배치하지 않는다 라는 선택도 경우의 하나에 속하므로 1. N = 1일 때, 1밖에 놓을 수 없으므로 경우는 1. N = 2일 때, 00, 11 두 개밖에 놓을 수 없으므로 2. 이제부터가 중요하다 . N = 3일 때, 100, 001, 111로 총 세가지이다. N이 홀 수라면,낱개로서 배치할 수 있는 타일인 "1"한개가 들어가는 경우가 생긴다. 그래서 경우의 수에 영향을 주게된다. 여기서 가만보면 어떤 점화식을 도출해낼 수가 있다. dp[i] = dp[i - 2] * 2 + dp[i-3] .. 이전 1 다음
