* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 문) 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입) 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출) 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 1. 테이블 정의 dp[k][n] = k개의 ..
* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 풀이 평소에는 Bottom-Up(for문) 방식을 택하여 많이 풀었는데, 오늘은 Top-Down(재귀) 방식으로 풀었다. 1. 테이블 정의 : P(N) = 마지막 정삼각형의 변의 길이 2. 점화식 : d[i] = d[i-1] + d[i-5]; 나선형으로 도는 삼각형의 값을 하나하나 나열하면서 규칙성을 찾았다. cf. 궁금해서 찾아본 다른 풀이 1~3까지의 값만 할당해주고 나머지는 d[i] = d[i-2] + d[i-3] 의 점화식 적용. 필자는 ..
* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 문) 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입) 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출) 첫째 줄에 경우의 수를 출력한다. 풀이 1. 테이블 정의 : dp[i] = 경우의 수 2. 점화식 dp[i] = dp[i-2] * dp[2] +{ dp[i-4]*2 + dp[i-6]*2 + ... + dp[0] *2 }; 3xn 타일이기 때문에, 짝수만 가능하다. 위의 점화식은 쉽게 말하면, 직전 값 *..
* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 문) 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의..
