[백준-9095번 자바/java] 1,2,3 더하기 _디버깅의 눈물

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

 

1, 2, 3 더하기 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

512 MB

85793

56148

38046

63.772%

문제

정수 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

 

---

 

체크 포인트

 

1. 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)

 -큰 문제를 여러 가지 작은 문제로 나누어 해결하는 DP(다이나믹 프로그래밍)을 이용했다.

-정수 n을 1,2,3의 합으로 나타내는 방법을 가장 작은 숫자들로부터 추론해보면,

 

우선

1은 {1} = 1개

2는 {1+1, 2} = 2개

3은 {1+1+1, 1+2, 2+1, 3} = 4개

...

로 이루어지는 것을 볼 수 있다.

 

이를 통해 볼 때, 4를 1,2,3의 합으로 나타내는 방법은,

 

(1을 1,2,3의 합으로 나타내는 경우의 수) + (2를 1,2,3의 합으로 나타내는 경우의 수) + (3을 1,2,3의 합으로 나타내는 경우의 수)

 

즉, 1+2+4 = 7로 볼 수 있다.

 

4가 되기 위해서는 어떤 숫자에 1,2,3 중 하나를 더해야 하는데, 

 

1)1에서 3을 더해 4가 된 경우(1을 1,2,3의 합으로 나타내는 경우) = 1 

2)2에서 2를 더해 4가 된 경우(2를 1,2,3의 합으로 나타내는 경우) = 2

3)3에서 1을 더해 4가 된 경우(3을 1,2,3의 합으로 나타내는 경우) = 4

 

로 경우의 수를 나눌 수 있기 때문이다.

 

그 결과

 

N을 1,2,3의 합으로 나타내는 경우의 수

=

(N-1)을 1,2,3의 합으로 나타내는 경우의 수 +

(N-2)을 1,2,3의 합으로 나타내는 경우의 수 +

(N-3)을 1,2,3의 합으로 나타내는 경우의 수

 

dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

 

 위의 식을 추론 할 수 있다.

 

 

 

 

 2.dp(다이나믹 프로그래밍) 배열의 초기화

 

    	int n = Integer.parseInt(st.nextToken());

    	dp = new int[n+1];

 

-문제를 처음 풀었을 때, dp배열의 초기 선언을 입력받은 숫자 +1 로 처리하였다. 이클립스에서는 문제없이 테스트케이스가 잘 작동했지만, 제출했을 때 런타임 에러(ArrayIndexOutOfBounds)가 발생했다.

-해당 원인을 찾으려고 했지만 찾을 수 없어서 추후 확인해봐야할 필요성이 있다.

 

-이후 문제에서 'n은 11보다 작은 양수'라고 크기를 한정한 것을 보고 

 

dp = new int[11];

 

위와 같이 초기화를 해준 결과 정답처리가 되었다.

 

 

풀이(bottom-up, 바텀업 방식)

 

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

public  class Main {
	
	static int[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	// 11보다 작은 양수 n 
    	int n = Integer.parseInt(st.nextToken());

    	// n은 11보다 작은 양수이기 때문에 배열의 크기를 11로 선언 
    	dp = new int[11];

    	// 1 2 3 4  5  6  7 -dp배열의 인덱스 
    	// 1 2 4 7 13 24 44 -1,2,3의 합으로 나타낼 수 있는 경우의 수 
    	// 다이나믹 프로그래밍 활용을 위한 초기 dp[1], dp[2], dp[3] 초기화 
    	dp[1] = 1;
    	dp[2] = 2;
    	dp[3] = 4;
    	
    	// 테스트 케이스 입력 
    	for(int i=0; i<n; i++) {
    		
	    	st = new StringTokenizer(br.readLine());
	    	
	    	int a = Integer.parseInt(st.nextToken());
	    	
	    	System.out.println(solution(a));

    	}
    }
    
    static int solution(int a) {
    	
    	// 4번부터 다이나믹 프로그래밍을 통해 답을 추론할 수 있다. 
    	for(int i=4; i<=a; i++) {
    		
    		dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    		
    	}
    	
    	return dp[a];
    } // end of solution 
    
} // end of Main