백준 15990 [자바] java 1, 2, 3 더하기 5

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

15990번: 1, 2, 3 더하기 5

▶문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

▶입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

---

▶출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

---

▶해설

동일한 수가 2번 이상 반복을 허용하지 않는 조건이 있습니다. 따라서 끝나는 숫자를 기준으로 개수를 셉니다. 

 

ex) 4

1 = dp [1][1] (1)  

2 = dp[2][2] (2) -> 1,1은 반복되므로 안됨

3 = dp[3][1] (2,1) + dp [3][2] (1,2) +dp [3][3] (3)

4 = dp[4][1] + dp [4][2] +dp [4][3]입니다.

 

이때 

dp [4][1]은 뒷자리에 1이 들어와야 하므로 2와3으로 끝나는 것을 더해주면 됩니다.

dp[4][1] = dp [3][2] + dp [3][3] 

마찬가지로 dp [4][2]와 dp[4][3]을 구합니다.

dp[4][2] = dp [2][1] + dp [2][3]

dp [4][3] = dp [1][2] + dp[1][2] 

 

따라서 점화식을 도출할 수 있습니다.

dp[j][1] = (dp[j-1][2] + dp[j-1][3])
dp[j][2] = (dp[j-2][1] + dp[j-2][3])
dp[j][3] = (dp[j-3][1] + dp[j-3][2])

N <=100,000 이므로 100000까지 dp를 미리 구해두고 입력이 들어오면 해당 값들을 더해서 출력합니다. 

 

전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        long result=0;
        long [][] dp = new long[100001][4];
        dp[1][1]=1;
        dp[2][2]=1;
        dp[3][1]=1;
        dp[3][2]=1;
        dp[3][3]=1;
        for(int j=4; j<=100000; j++){
            dp[j][1] = (dp[j-1][2] + dp[j-1][3])%1000000009;
            dp[j][2] = (dp[j-2][1] + dp[j-2][3])%1000000009;
            dp[j][3] = (dp[j-3][1] + dp[j-3][2])%1000000009;
        }
        for(int i=0; i<t; i++){
            int k = Integer.parseInt(br.readLine());
            result = (dp[k][1]+dp[k][2]+dp[k][3])%1000000009;
            System.out.println(result);
        }
    }
}