[백준] 1, 2, 3 더하기 6 (!) (15991번 JAVA)

[백준]  1, 2, 3 더하기 6 (!) (15991번 JAVA)

---

[접근 방법]

이 문제의 점화식을 찾는 것은 굉장히 어렵다. (내 기준)

주먹구구식으로 계속해서 구해보았다.

dp[1] = 1; // 1
dp[2] = 2; // 1+1, 2
dp[3] = 2; // 1+1+1, 3
dp[4] = 3; // 1+1+1+1, 1+2+1, 2+2
dp[5] = 3; // 1+1+1+1+1, 1+3+1, 2+1+2
dp[6] = 6; // 1+1+1+1+1+1, 1+1+2+1+1, 1+2+2+1, 2+1+1+2, 2+2+2, 3+3

dp[7] 은 문제에서 주어진대로, 6이다.

dp[7] = dp[5] + dp[3] + dp[1] 이 성립한다.

dp[n] = dp[n-2] + dp[n-4] + dp[n-6] (단, n>=7)

의 점화식을 유추할 수 있다.

 

확인을 위해서 dp[8] = dp[6] + dp[4] + dp[2] 을 구하였다.

dp[8] = 11 이 된다.

예제 처럼, dp[10] = 20 이 성립하는지 확인하였다.

dp[10] = 11 + 6 + 3 = dp[8] + dp[6] + dp[4] 가 성립한다.

 

따라서, 점화식은 

dp[n] = dp[n-2] + dp[n-4] + dp[n-6] (단, n>=7)

라고 할 수 있다.

 

---

[JAVA 코드]

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

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        
        long[] dp = new long[100_001];
        dp[1] = 1; // 1
        dp[2] = 2; // 1+1, 2
        dp[3] = 2; // 1+1+1, 3
        dp[4] = 3; // 1+1+1+1, 1+2+1, 2+2
        dp[5] = 3; // 1+1+1+1+1, 1+3+1, 2+1+2
        dp[6] = 6; // 1+1+1+1+1+1, 1+1+2+1+1, 1+2+2+1, 2+1+1+2, 2+2+2, 3+3 

        for(int i=7; i<=100_000; i++){
            dp[i] = (dp[i - 2] + dp[i - 4] + dp[i - 6]) % 1_000_000_009;
        }

        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n] + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 

=> 점화식이 도저히 보이지 않는다면, 주먹구구식으로 일단 구해보자!

 

위와 같은 조건이 붙는다면 long 자료형을 사용해야 할 확률이 높다.