[백준] p9095 1, 2, 3 더하기 : 동적계획법

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1 

3
4
7
10

예제 출력 1

7
44
274

 

 동적계획법은 문제를 작은 문제로 쪼개어, 작은 문제의 해답을 이용해 큰 문제를 해결하는 방법이다.

'작은 문제들의 해답을 미리 저장하고, 동일한 해답이 다시 필요한 경우 재활용'함으로써, 속도를 최적화할 수 있다.

이렇게 재활용 하여 반복되는 부분은 한번만 하도록 하는 방식을 메모이제이션 이라고 한다. 

동적계획법을 푸는 방법으론 크게 두가지가 있는데, 재귀와 반복문을 사용하는 것이다. (top-down방식과 bottom-up방식)

 

만약 n=4 이면

맨앞에 1을 놓았을 때

1+3 = 4

1 + 1+2 = 4

1 + 1 +1+1 = 4

...

 

n을 1,2,3의 합으로 나타내는 경우의 수 dp[n]은 맨 앞에 각각 1,2,3을 놓았을 때,

나머지 부분의 경우의 수들의 합이다.

4 = 1+3일때 3(=4-1)을 만드는 방법은 dp[3]가지 이다. 

4 = 2+2일때 2(4-2)를 만드는 방법은 dp[2]가지가 있다. 

4 = 3+1일때 1(=4-3)을 만드는 방법은 dp[1]가지가 있다. 

즉, dp[4] = dp[3]+dp[2]+dp[1] 이다. 

 

맨 앞에 1을 놓았을 경우, n-1의 경우의 수 이기 때문에 dp[n-1]이고,

멘 앞에 2를 놓았을 경우, n-2의 경우의 수 이기 때문에 dp[n-2]이고, 

멘 앞에 3를 놓았을 경우, n-3의 경우의 수 이기 때문에 dp[n-3]이 된다.

그렇다면 다음과 같은 식을 세울 수 있다.

if(n==1): dp[1] = 1 1 ->1가지

if(n==2): dp[2] = 2 1+1 / 2 ->2가지

if(n==3): dp[3] = 4 1+1+1 / 1+2 / 2+1 / 3 ->4가지

 if(n>=4): dp(n) = dp(n-1)+dp{n-2}+dp{n-3)

 

재귀로 구현하면 아래와 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램
//dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
public class Main {
	static int[] dp;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while(T-- >0) {
			int n = Integer.parseInt(br.readLine());
			dp = new int[n+1];

			sb.append(dp(n)).append("\n");
		}

		System.out.print(sb);
	}

	static public int dp(int n) {

		if(n==1) return dp[1] = 1;
		if(n==2) return dp[2] = 2;
		if(n==3) return dp[3] = 4;

		//if(n>=3)
		dp[n] = dp(n-1) + dp(n-2) + dp(n-3);

		return dp[n];
	}

}​