[백준 9095번][Java] 1, 2, 3 더하기

문제

 

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

 

---

 

풀이

 

n일 때의 값을 생각해보자

1, 2, 3의 수만 사용할 수 있고, 순서가 다른 방법을 독립적인 방법으로 친다는 것을 생각해야한다

 

무작정 하나씩 세기에는 알고리즘의 속도도, DP의 방법론도 맞지 않는 것 같다

 

그렇다면 이미 세어진 갯수에서 +1, +2, +3 을 뒤에다 붙이는 방법은 어떨까?

 

dp[3]

1 1 1

2 1

1 2

3

일 때,

 

dp[4]

1 1 1 +1

2 1 +1

1 2 +1

3 +1

임을 알 수 있다

 

같은 방법으로 dp[1]에 +3, dp[2]에 +2, dp[3]에 +1 을 붙인다면

dp[4] = dp[1] + dp[2] + dp[3] 임을 알 수 있고

dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 점화식이 도출되는 것을 알 수 있다 

 

---

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());
        int N;
        
        for(int t=0 ; t<T ; t++) {
            N = Integer.parseInt(bf.readLine());
            
            for(int i=4 ; i<=N ; i++) {
                if(dp[i] == 0)
                    dp[i] = dp[i-1] + dp[i-2] +dp[i-3];
            }
            
            System.out.println(dp[N]);
        }
    }
}