1, 2, 3 더하기 3 : 15988 - JAVA

---

1. 문제 링크

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

---

2. 문제 설명

---

3. 문제 접근

-dp문제는 주로 규칙성을 찾고 점화식을 작성하는 것이 핵심이다!!

 

(1) 문제의 규칙성을 확인하기 위해 표를 작성해서 비교!

N	1	2	3	4(합계)
1	1	0	0	1
2	1	1	0	2
3	2	1	1	4
4	4	2	1	7
5	7	4	2	13
6	13	7	4	24
7	24	13	7	44
8	44	24	13	81
9	81	44	24	149

 

(2) 표에 표시한 값들의 규칙을 확인해보기[하단 표 색깔끼리 비교해보기]

N	1	2	3	4(합계)
1	1	0	0	1
2	1	1	0	2
3	2	1	1	4
4	4	2	1	7
5	7	4	2	13
6	13	7	4	24
7	24	13	7	44
8	44	24	13	81
9	81	44	24	149

※규칙성(N >= 4)

-(N,1) = N-1의 합

-(N,2) = N-2의 합

-(N,3) = N-3의 합

 

 

(3)규칙성 확인 후, 점화식 작성

dp[row][1] = dp[row-1][4];

dp[row][2] = dp[row-2][4];

dp[row][3] = dp[row-3][4];

 

---

4. 문제 풀이

 

import java.util.Scanner;
 
public class sumOf123_3_2 {
    static long div = 1000000009;
    static long [] dp = new long[1000001];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
        
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for (int tc = 1; tc <= T; tc++) {
            int    data = Integer.parseInt(sc.nextLine());
            
            for (int row = 4; row <= data; row++) {
                dp[row] = (dp[row-1] + dp[row-2] + dp[row-3]) % div;
            }
            
            long sum = dp[data];
            System.out.println(sum);
        }
 
        sc.close();
    }
}
 

 

---

5. 느낀점 또는 개선사항

처음에는 점화식 문제 1도 못건드렸는데, 계속 문제를 풀다보니 규칙성을 하나씩 찾을 수 있는 것 같다.

하지마, 아직 재귀함수 형태로 코드 작성하는 것에는 아직 어려움이 있다;