[백준-9095]-[다이나믹프로그래밍] - 1,2,3 더하기

문제링크 :  https://www.acmicpc.net/problem/9095

이문제는 다이나믹프로그래밍 공부하다보면 제일 기본문제로 나오는 문제이다.

이런 문제가 공통점을 찾고 점화식 구하기가 제일 쉽다. 이런문제만 나왔으면 좋겠다.

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

숫자 1, 2, 3 으로 원하는 정소 n 을 만드는 경우의 수를 구하라 이다. 

예제로 주어진 4로 구해보면

1+1+1+1 , 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1  총 7가지의 경우의 수가 있다고 한다.

이중에서 끝이 1로 2로 3으로 끝나는 것들을 분류해보면

1로 끝나는 경우들 : 

1+1+1+1

1+2+1

2+1+1

3+1

2로 끝나는 경우들 :

1+1+2

2+2

3(으)로 끝나는 경우들 :

1+3

1로 끝나는 경우에서 마지막 + 1 을 제외한다면 3을 구하는 경우의 수이다.

2로 끝나는 경우에는 2를 구하는 경우의 수이다.

3으로 끝나는 경우는 1을 구하는 경우의 수이다.

다풀었다. 이건 쉽다.

T(4) = T(3) + T(2) + T(1) 의 값이며 점화식은

T(N) = T(N-1) + T(N-2) + T(N-3) 으로 입력 받은 정수 N의 경우의 수를 구할 수 있다.

1 의 경우의 수는 1

2 의 경우의 수는 2

3 의 경우의 수는 4

합하면 7

이제 코딩을 해보자.

import java.util.Scanner;
 
public class E_9095 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        // 입력받을 정수 N 의 최대 값이 10이므로 배열의 크기는 10+1 로생성한다.
        int[] arr = new int[11];
        
        arr[0] = 1; // 기본값으로 가지고 있는 것 출력되지않는 인덱스
        
        for(int i=1; i <= 10; i++) {
            //1 이 마지막인것
            if(i-1 >= 0)
                arr[i] += arr[i-1];
            
            //2 가 마지막인것
            if(i-2 >= 0)
                arr[i] += arr[i-2];
            //3 이 마지막인것
            if(i-3 >= 0)
                arr[i] += arr[i-3];
        }
        
        for(int i=0; i < cnt; i++) {
            int num = sc.nextInt();
            
            System.out.println(arr[num]);
        }
    }
}