문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유사한 문제들은 많이 풀어보았다. 1, 2, 3을 만들 수 있는 경우의 수를 dp테이블에 베이스로 저장해둔다. 점화식은 다음과 같다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (3
문제 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 이전에 풀었던 오르막 수 문제의 쉬운 버전 문제다. dp[n][0] = 0으로 끝나는 n자리 이친수의 개수 dp[n][1] = 1로 끝나는 n자리 이친수의 개수 문제에 주어진 조건을 살펴보자. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 1번 조건에 의해 dp[1][0] = 0, dp[1][1] = 1이 성립..
