[백준OJ] 15991번 1, 2, 3 더하기 6 - Java

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

15991번: 1, 2, 3 더하기 6

---

풀이

DP를 이용해서 문제를 해결했습니다.

DP[N] = 조건에 맞춰서 N을 만드는 경우의 수 입니다.

 

먼저 차근차근 규칙을 찾아가봅시다

1 = 1

2 = 1+1 / 2

3 = 1+1+1 / 3

4 = 1+1+1+1 / 2+2

5 = 1+1+1+1+1 / 1+3+1

6 = 1+1+1+1+1+1 / 1+2+2+1 / 1+1+2+1+1 / 2+2+2 / 3+3

 

6을 기준으로 규칙을 살펴보면

1+(조건에 맞게 4를 만드는 경우)+1 => 1+(1+1+1+1)+1 / 1+(1+2+1)+1

2+(조건에 맞게 2를 만드는 경우)+2 => 2+(2)+2

3+(조건에 맞게 0을 만드는 경우)+3 => 3+(0)+3

로 정리를 할 수 있습니다.

 

N을 기준으로 규칙을 살펴보면

1+(조건에 맞게 N-2를 만드는 경우)+1 => DP[N-2]의 양옆에 1을 붙이는 경우

2+(조건에 맞게 N-4를 만드는 경우)+2 => DP[N-4]의 양옆에 2를 붙이는 경우

3+(조건에 맞게 N-6을 만드는 경우)+3 => DP[N-6]의 양옆에 3을 붙이는 경우

 

 

이 규칙에 맞춰서 점화식을 세워보면

DP[N] = DP[N-2] + DP[N-4] + DP[N-6] ; (단 각 인덱스가 음수가 나올 경우에는 0으로 대체)

 

시간복잡도

O(N)

 

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long[] dp = new long[100001];
        dp[0]=1;
        dp[1] = 1;//1
        dp[2] = 2;//1+1,2
        dp[3] = 2;//1+1+1,3

        for (int i = 4; i <= 100000; i++) {
            dp[i] = ((i - 2 >= 0 ? dp[i - 2] : 0) + (i - 4 >= 0 ? dp[i - 4] : 0) + (i - 6 >= 0 ? dp[i - 6] : 0)) % 1000000009;
        }

        int T = Integer.valueOf(br.readLine());
        while (T-- > 0) {
            int n = Integer.valueOf(br.readLine());
            sb.append(dp[n]).append("\n");
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
    }
}