[백준] 9095 - 1,2,3더하기 (java)

9095번: 1, 2, 3 더하기

 

---

 

문제내용

첫번째 줄은 테스트 케이스 수이고 두번째 줄부터 각 테스트 정수 n이 주어진다.

1,2,3의 합으로 정수 n을 구하는 수를 출력하자. (한개 이상 수를 사용해야한다)

 

문제풀이

아래는 1부터 4까지 가지는 조합의 수이다.

n=1 :
1

n=2 :
1+1 
2

n=3 :
1+1+1
2+1 
1+2 
3

n=4 :
1+1+1+1 // (n-1)+1
1+2+1
2+1+1
3+1
1+1+2 // (n-2)+2
2+2
1+3 // (n-3)+3

만약 n=4의 조합의 수는 아래와 같다.

n=3의 조합의 수에 +1를 한 값들

n=2의 조합의 수에 +2를 한 값들

n=3의 조합의 수에 +3을 한 값들로 구성되어 있다.

 

따라서 dp에 각각 조합의 수를 저장하고 

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 점화식을 사용한다.

---

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

// https://www.acmicpc.net/problem/9095
// 1, 2, 3 더하기
public class B9095 {
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new int[16];
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(br.readLine());
            System.out.println(calc(a));
        }
    }

    private static int calc(int a) {
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= a; i++) {
            dp[i] = dp[i-1] + dp[i-2]+ dp[i-3];
        }
        return dp[a];
    }
}