[BOJ] 백준 9095번 1,2,3 더하기 (Java)

#9095 1,2,3 더하기

난이도 : 실버 3

유형 : DP

9095번: 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의 합으로 나타내는 방법의 수를 출력한다.

 

문제 풀이  

DP 문제로 점화식을 도출해내어 푸는 문제이다.

 

규칙 도출해내기

정수 n이 주어졌을 때, 1,2,3의 합으로 나타내는 방법의 수를 구해보자.

 

정수 n	방법의 수(dp)	케이스
1	1	1
2	2	1+1, 2
3	4	1+1+1, 1+2, 2+1, 3
4	7	( 1+1+1+1, 1+1+2, 1+2+1, 1+3 ), (2+1+1, 2+2), (3+1)
5	13	(1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+1+3, 1+2+1+1, 1+2+2, 1+3+1), (2+1+1+1, 2+1+2, 2+2+1, 2+3), (3+1+1, 3+2)

 

위의 표를 통해 도출해낼 수 있는 규칙은 4이상의 정수 n은 1, 2, 3을 뺀 정수들의 방법의 수에 각 숫자를 더해준 방법의 수와 일치하다는 것이다.

• 정수 4를 보면 1+(dp[3] 케이스), 2+(dp[2] 케이스), 3+(dp[1] 케이스) =  4 + 2 + 1 = 7
• 정수 5를 보면 1+(dp[4] 케이스), 2+(dp[3] 케이스), 3+(dp[2] 케이스) =  7 + 4 + 2 = 13

따라서 점화식은 다음과 같다.

• if(i>=4), dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

풀이 코드 

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		int[] dp = new int[11];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		for(int i=4; i<11; i++) {
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
		}
		for(int i=0; i<t; i++) {
			int num = Integer.parseInt(br.readLine());
			System.out.println(dp[num]);
		}
	}
}