[백준 9095번 : 실버3] 1,2,3 더하기 (DP / Java)

이번 문제는 DP라고 해서 1부터 값을 저장하는건가? 까지 생각을 했지만 그 생각이 답까지 이어지진 못했다.

그래서 결국 답을 확인해봤다. 

 

 

문제부터 살펴보자.

 

문제

정수 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부터 값을 저장하는것은 맞다. 하지만 거기서의 규칙을 찾는것이 관건이다.

그래서 이번 문제는 1부터 정수 n까지 한번 구해보는것이다.

 

1

1

-> 1개

 

2

1+1

2

-> 2개

 

3

1+1+1,

1+2,

2+1,

3

-> 4개

 

4

1+1+1+1,

1+1+2,

1+2+1,

2+1+1,

2+2,

3+1,

1+3

-> 7개

 

5

1+1+1+1+1,

1+1+1+2,

1+1+2+1,

1+2+1+1,

2+1+1+1,

1+2+2,

2+2+1,

2+1+2,

1+1+3,

1+3+1,

3+1+1,

2+3,

3+2

->13개

 

이제보면 규칙이 점점 나오기 시작했다.

 

4는

1+2+4 = 7개가 되었고

 

5는

2+4+7 = 13개가 되었다.

 

즉 

해당 숫자는 

-3까지의 모든 방법을 더한수가 해당 숫자의 방법의 수가 되는것이다.

 

따라서 소스를 보면 아래와 같이 된다.

		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		//초기값을 이용하여 나중의 값을 구한다
		for(int i = 4;i<dp.length;i++) {
			dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
		}

 

 

그래서 전체 소스를 보자면 아래와 같다.

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		
		int cases = sc.nextInt();
		int[] nums = new int[cases];
		for(int i = 0; i<nums.length;i++) {
			nums[i] = sc.nextInt();
		}
		
//		int cases = 3;
//		int[] nums = {4,7,10};
		
		int[] dp = new int[12];
		
		//dp에 초기값을 넣는다.
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		//초기값을 이용하여 나중의 값을 구한다
		for(int i = 4;i<dp.length;i++) {
			dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
		}
		
		for(int i = 0; i<nums.length;i++) {
			System.out.println(dp[nums[i]]);
		}
	}
}

 

 

느낀점

1. DP는 이전 케이스 값을 무조건 구해봐야한다.