백준 9095번 1, 2, 3 더하기 (java)

[Silver III] 1, 2, 3 더하기 - 9095

문제 링크

성능 요약

메모리: 15852 KB, 시간: 112 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 2일 02:39:59

문제 설명

정수 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. 완전탐색

2. 다이나믹 프로그래밍

 

완전탐색부터 살펴보자.

 

그냥 말 그대로 나올 수 있는 모든 경우의 수를 다 검사하는 방법이다.

 

T의 범위가 정해져있지 않아서 시간 복잡도를 계산할 수 없는 문제였기에 일단 완전탐색으로 풀어봤는데 모든 테스트 케이스가 통과 됐다.

 

완전탐색으로 풀 경우 nCr이 아닌 nPr 로 풀어야 한다.

 

순서가 다른 조합은 다른 경우의 수로 판단하기 때문이다.

 

완전탐색 코드

public class Main {
    static int N=0,cnt=0;
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for(int i = 0 ;i<T;i++) {
            N = Integer.parseInt(br.readLine());

            dfs(0);
            bw.write(cnt + "\n");
            bw.flush();

            cnt = 0;
        }


    }

    static void dfs(int depth){
        if(depth >= N) {
            if (depth == N) {
                cnt++;
            }
            return;
        }

        for(int  i =1;i<4;i++){
            dfs(depth+i);
        }
    }
}

 

다이나믹 프로그래밍 풀이

 

간단하게 생각해보자, 

 

1 = 1   한 가지 경우의 수다

 

2 = 1 + 1,

      2

 

두 가지가 나온다.

 

3 =

1 + 2

1 + 1 + 1

2 + 1

3

 

4 가지가 나온다 규칙성이 보이지 않는가?

 

2의 경우 1에서 나온 케이스에 1을 더해준 후 , 그냥 2 하나만 있는 경우 한 가지만 더해주면 모든 경우의 수가 나온다.

 

3의 경우 (1에서 나온 케이스에 2를 더한 경우의 수)   +    (2에서 나온 케이스에 1을 더한 경우의 수)    +   3 한 가지 경우

와 같다.

 

4의 경우는  (1에서 나온 케이스에 3를 더한 경우의 수)   +    (2에서 나온 케이스에 2를 더한 경우의 수)   +

(3에서 나온 케이스에 1을 더한 경우의 수) 로 나타낼 수 있다.

 

고로 dp[N] = dp[N-1] + dp[N-2] + dp[N-3]  의 점화식이면 문제가 해결된다.

 

다이나믹 프로그래밍 코드

public class Main {
    static int N=0,dp[], cnt=0;
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for(int i = 0 ;i<T;i++) {
            N = Integer.parseInt(br.readLine());

            int dp[] = new int[N+3];

            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            if(N > 3) {
                for (int j = 4; j <=N;j++){
                    dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
                }
            }

            bw.write(dp[N] + "\n");
            bw.flush();

            cnt = 0;
        }


    }
}