백준 9095 - 1, 2, 3 더하기 ( Java )

made by : besforyou

 

 

문제풀이

 

n을 입력받고, n을 1, 2, 3의 합으로 나타내는 모든 경우를 구할 필요없이 

과거 기록을 이용하는 dp 알고리즘을 이용하여 해결하면 편리합니다.

 

 

- n이 1인 경우 1, 2, 3의 합으로 나타내는 방법

 

1 

: 1가지

 

- n이 2인 경우 1, 2, 3의 합으로 나타내는 방법

 

1 1

2

: 2가지

 

- n이 3인 경우 1, 2, 3의 합으로 나타내는 방법

 

1 1 1

1 2

2 1

3

: 4가지

 

- n이 4인 경우 1, 2, 3의 합으로 나타내는 방법

 

1 1 1 1

1 2 1

2 1 1

3 1

1 1 2

2 2

1 3

: 7가지

 

n이 4인 경우를 보면 

3을 1, 2, 3의 합으로 나타낸 모든 경우 + 1

2을 1, 2, 3의 합으로 나타낸 모든 경우 + 2

1을 1, 2, 3의 합으로 나타낸 모든 경우+ 3

된것을 볼 수 있다.

 

1 1 1 1

1 2 1

2 1 1

3 1

1 1 2

2 2

1 3

 

 

이를 통해 n이 주어졌을때 1, 2, 3의 합으로 나타내는 방법은 

( n -1 경우의 수 + n - 2 경우의 수 + n - 3 경우의 수 )개수 만큼 존재한다는것을 알 수 있다.

즉, dp를 위한 점화식이 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이라고 할 수 있다.

 

 

 

코드

 

import java.io.*;
 
public class Main {
    static int MAX = 16;
    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());
 
        int dp[] = new int[MAX];
 
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        dp[4] = 7;
 
        for (int i = 5 ; i < MAX ; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
 
        for (int i = 0 ; i < T ; i++) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n] + "\n");
        }
 
        bw.flush();
        bw.close();
    }
}

 

결과