반응형 백준 21931 [DP] 백준 2193 이친수 (Pinary Number) BackJoon # 2193 - 이친수 (Pinary Number) https://www.acmicpc.net/problem/2193 대표적인 DP문제입니다. DP[N] 을 N개 자리수에 이친수를 만족하는 경우의 수라고 생각하겠습니다.N자리에 올 수 있는 숫자는 0 OR 1입니다. 각각에 경우에 대해서 생각해 보겠습니다. N자리에 0인 경우 N-1자리에 올 수 있는 숫자는 0 OR 1 둘 다 가능합니다. 따라서 DP[N] = DP[N-1] 이 성립합니다. N자리에 1인 경우 N-1자리에 올 수 있는 숫자는 0 만 가능합니다. 그렇다면 N-2 자리에 올 수 있는 숫자는? 0 OR 1 이 가능합니다. 따라서 . . . DP[N] = DP[N-2] 이 성립합니다. 이제 N자리에 0 이 올수도 1이 올수도 있으.. 2017. 10. 25. 이전 1 다음 반응형
