15991 1, 2, 3 더하기 6 JAVA

 

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

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

 

우선 나는 이 문제를 처음부터 풀이하기엔 너무 번거로워서 아예 접근법을 모르시겠다면 이전에 작성한 1, 2, 3 더하기 포스팅을 확인하여주시면 좋을것 같다.

 

지난 1, 2, 3 더하기 5 문제에선 작은 문제와 큰 문제의 작은 문제가 동일하지 않은 경우를 이용하여 연속되지 않은 수들로 구성된 식의 수를 구할 수 있었다.

 

이번 문제는 이전 문제를 풀고 나서, 문제를 힐끔보고 자기전에 영화를 보다가 순간 생각이 번뜩여서 풀었던 문제이다 ㅋㅋㅋㅋㅋ

 

이번 문제는 대칭이 되어야만 한다.

그렇담 어떻게 대칭을 구할 수 있을까? 

 

만약 n이 4일 때, 1 + 1 + 1 + 1;의 식에서 작은 문제는 여전히 해당 식에서 마지막에 더하는 식이고, 여기서 하나의 조건을 더 추가했다.

"해당 식의 맨 앞의 숫자와 뒤의 숫자가 동일한 경우라면?"을 이용해서 답을 구했다.

 

아래는 해당 문제의 사이트에 올라온 4로 올 수 있는 식이다.

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

위와 같이 앞과 뒤의 숫자가 동일하고 중간에 올 수 있는 식의 수를 dp를 이용하여 구할 수 있다.

 

package BJLecture.AlgoBasic1.DP;

import java.io.*;
public class D15991 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long[][] dp = new long[100001][4];
        long max = 1000000009L;
        dp[0][0] = 1;
        for(int i = 1; i < dp.length; i++) {
            if(i == 1)
                dp[i][1] = 1;
            else
                dp[i][1] = dp[i-2][0] % max;

            if(i == 2)
                dp[i][2] = 1;
            else if(i -4 >= 0)
                dp[i][2] = dp[i-4][0] % max;

            if(i == 3)
                dp[i][3] = 1;
            else if(i -6 >= 0)
                dp[i][3] = dp[i-6][0] % max;

            dp[i][0] = dp[i][1] + dp[i][2] + dp[i][3];
        }

        int t = Integer.parseInt(br.readLine());
        while(t --> 0) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n][0] % max + "\n");
        }
        bw.flush();
    }
}

 

이번 문제는 약간 예외처리를 잘 신경 써주어야 한다. 이에 주의를 해야하고, 왜 [i-2] [i-4] [i-6]과 같이 연산하였냐면

 

n이 8일 때, 

1. 앞 뒤가 1인 경우 중간에 올수 있는 수들의 합 : 8 - 1 - 1     >> 6
2. 앞 뒤가 2인 경우                  ""                    : 8 - 2 - 2.   >> 4
3. 앞 뒤가 3인 경우                  ""                    : 8 - 3 - 3.   >> 2

 

해당 포스팅이 여러분에게 조금이나마 도움이 됐다면 좋겠다