[백준/JAVA] 15990번: 1, 2, 3 더하기 5

📖 문제

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

 

 

 

💡  풀이 방식

• DP

 

같은 숫자가 2번 이상 연달아 나오면 안 된다는 조건이 있으므로,

마지막 숫자를 기준으로 갯수를 센다.

 

 

예) 4

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

2 = dp[2][2] (2)

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[3][2] + dp[3][3]) + (dp[2][1] + dp[2][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]

 

 

 

🔺 코드

import java.io.*;
 
public class Main {
    static final int MOD = 1_000_000_009;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        long[][] dp = new long[100_001][4];
        
        dp[1][1] = 1; // 1
        dp[2][2] = 1;  // 2
        dp[3][1] = 1;  // 2+1
        dp[3][2] = 1;  // 1+2
        dp[3][3] = 1;  // 3
        
        for(int i = 4 ; i <= 100_000 ; i++) {
            dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % MOD;
            dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % MOD;
            dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % MOD;
        }
        
        StringBuilder sb = new StringBuilder();
        while(T --> 0) {
            int num = Integer.parseInt(br.readLine());
            sb.append((dp[num][1] + dp[num][2] + dp[num][3]) % MOD).append("\n");
        }
        System.out.println(sb.toString());
    }
}
 

 

---

💦 어려웠던 점

- 점화식 찾기,, 하하하하

 

 

🧐 새로 알게 된 내용

- dp 식 2차원으로 세우기,,,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

 

---

(참고)

이해용

[백준 15990번] 1, 2, 3 더하기 5 (java)

 

- 풀이 참고

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

백준 15990 - 1,2,3 더하기5 [DP/JAVA]

 

[알고리즘] 백준 15990 1, 2, 3 더하기 (5) Java