[백준 2193] 이친수
https://www.acmicpc.net/problem/2193 이진수 10이 존재할때 1을 1번째 자리 수, 0을 2번째 자리수와 같이 표현할 수 있다.n번째 자리수가 0이라면 n-1번째 자리수는 0또는 1이고, n번째 자리수가 1이라면 n-1번째 자리수는 0이다.즉 n번째 자리수가 0일 경우의 수는 n-1번째 자리수가 0일 경우의 수와 1일 경우의 수의 합이고n번째 자리수가 1일 경우의 수는 n-1번째 자리수가 0일 경우의 수와 같다. 점화식arr[n][m] : n번째 자리수가 m일 경우의 수arr[0][0] = 0arr[0][1] = 1arr[n][0] = arr[n-1][0] + arr[n-1][1]arr[n][1] = arr[n-1][0] C++ code길이 N=90인 이친수는 2,880,06..
알고리즘
2019. 3. 4. 18:28
[백준 10844] 쉬운 계단 수
https://www.acmicpc.net/problem/10844 45656 이라는 숫자가 존재한다고 할때 4는 1번째 자리 수, 5는 2번째 자리 수 6은 3번째 자리 수, 5는 4번째 자리 수, 6은 5번째 자리 수로 표현할 수 있다.n번째 자리 수가 0일경우 n+1번째 자리수는 1만 가능하며 n번째 자리 수가 9일 경우 n+1번째 자리수는 8만 가능하다.n번째 자리 수가 1~8인 경우는 n+1번째 자리수에 각각 2개의 숫자가 존재할 수 있다. (예: n번째 자리 수가 1인경우 0 또는 2, n번째 자리 수가 4인경우 3 또는 5)즉,n+1번째 자리에서 0이 나올 수 있는 경우의 수
알고리즘
2019. 3. 4. 16:50