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

문제

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

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

 

문제 이해

백준의 1, 2, 3 더하기 시리즈 중 5번 문제입니다.

정수 n이 주어졌을 때, n을 1, 2, 3 (3개의 수)의 합으로 나타내는 방법의 수를 구하는 문제입니다. 다만, 같은 수를 두 번 이상 연속해서 사용하면 안 된다는 조건이 있습니다.

방법의 수를 1,000,000,009로 나눠야 한다는 점과 n이 1이상 100,000 이하라는 점에서 다이나믹 프로그래밍(Dynamic Programming)으로 풀어야 한다고 생각했습니다.

 

풀이

 

①

먼저 같은 수를 두 번 이상 연속해서 사용하면 안 된다는 조건이 없다고 생각해 봅니다.

그렇다면 n을 만들 수 있는 방법의 수를 dp[n]이라 하면,

dp[n] = dp[n-1] + 1

dp[n] = dp[n-2] + 2

dp[n] = dp[n-3] + 3

dp[n]은 위 3 경우로 구성되기 때문에, dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이라는 점화식을 도출할 수 있습니다.

 

②

①번에서 세운 점화식에 같은 수를 두 번 이상 연속해서 사용하면 안 된다는 조건을 추가해봅시다.

dp[n] = dp[n-1] + 1에서 dp[n-1]을 만드는 식이 n-1 = a + b + c (여기서 a, b, c는 1, 2, 3 중 하나임)이라 하면, 마지막 자리의 숫자인 c가 1이면 연속으로 1이 나오므로 조건에 위배됩니다. +2, +3 또한 c가 2, 3이라면 조건에 위배됩니다.

이 문제를 해결하기 위해, dp 배열을 이차원 배열로 바꿔줍니다.

dp[n][k] : 정수 n를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막 자리의 숫자는 k(k는 1, 2, 3 중 하나임)

 

③

②에서 만든 이차원 배열을 가지고 점화식을 세웁니다.

 i) dp[n][1] = dp[n-1][2] + dp[n-1][3]

 ii) dp[n][2] = dp[n-2][1] + dp[n-2][3]

 iii) dp[n][3] = dp[n-3][1] + dp[n-3][2]

i)을 예시로 하면 n = a + b + 1 이면 n = a + (2 또는 3) + 1의 형태로 구성됩니다.

 

④

③의 iii) 식의 dp[n-3][1]과 dp[n-3][2]을 위해 n은 1부터 3까지의 초기값을 구해봅니다.

 i) n = 1인 경우

 1 = 1

 => 식의 마지막 자리의 숫자가 1로 끝나는 하나의 경우밖에 없기 때문에 dp[1][1] = 1 임을 알 수 있습니다.

 ii) n = 2인 경우

 2 = 2

 => 식의 마지막 자리의 숫자가 2로 끝나는 하나의 경우밖에 없기 때문에 dp[2][2] = 1 임을 알 수 있습니다.

 iii) n = 3인 경우

 3 = 2 + 1

 3 = 1 + 2

 3 = 3

 => 식의 마지막 자리의 숫자가 각각 1, 2, 3으로 끝나는 총 3개의 경우가 존재하고 dp[3][1] = dp[3][2] = dp[3][3] = 1 임을 알 수 있습니다.

 

위에서 언급하지 않은 dp[1][2], dp[1][3], dp[2][1], dp[2][3]는 모두 불가능한 경우이기 때문에 0이 됩니다.

 

⑤

 i) dp[n][1] = dp[n-1][2] + dp[n-1][3]

 ii) dp[n][2] = dp[n-2][1] + dp[n-2][3]

 iii) dp[n][3] = dp[n-3][1] + dp[n-3][2]

 위에서 세운 점화식을 i = 1~n까지 진행한 후 dp[n][1] + dp[n][2] + dp[n][3]을 구하면 문제에서 원하는 정답을 얻을 수 있습니다.

 

+

 처음 이 문제를 풀 때 테스트 케이스마다 i = 1~n까지 구하였더니 시간 초과가 발생하였습니다.

그래서 테스트 케이스의 개수를 입력받기 전에 n의 Max값인 100,000까지 한 번에 구한 뒤에 테스트 케이스마다 저장해둔 값을 활용하여 출력했더니 통과되었습니다.

 

+

 테스트 케이스의 개수인 T의 범위가 문제에서 주어지진 않았지만, StringBuilder를 활용하여 출력 값을 저장해둔 뒤 한 번에 출력하면 실행시간을 좀 더 단축시킬수 있었습니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static int T, n, div, limit, ans;
    static int[][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        
        div = 1000000009; //div: 방법의 수를 나누는 값
        limit = 100000; //limit: 정수 n의 최댓값
        dp = new int[limit+1][4]; //dp[i][j]: 정수 i를 만드는데 마지막 자리의 숫자는 j인 방법의 개수
        dp[1][1] = dp[2][2] = dp[3][3] = dp[3][1] = dp[3][2] = 1;
        for(int i = 4; i<=limit; i++) {
            for(int j = 1; j<=3; j++) {
                //j가 1이면, 정수 i-1를 만드는데 마지막 자리의 숫자는 2 또는 3인 방법의 개수의 합
                if(j==1) dp[i][j] = dp[i-1][2] + dp[i-1][3];
                //j가 2이면, 정수 i-2를 만드는데 마지막 자리의 숫자는 1 또는 3인 방법의 개수의 합 
                else if(j==2) dp[i][j] = dp[i-2][1] + dp[i-2][3]; 
                //j가 3이면, 정수 i-1를 만드는데 마지막 자리의 숫자는 1 또는 2인 방법의 개수의 합
                else dp[i][j] = dp[i-3][1] + dp[i-3][2]; 
                dp[i][j] %= div;
            }
        }
        T = Integer.parseInt(br.readLine().trim()); //T: 테스트 케이스의 개수
        for(int tc = 1; tc<=T; tc++) {
            n = Integer.parseInt(br.readLine().trim()); //n: 입력값
            ans = 0; //ans(출력값): 정수 n을 1,2,3의 합으로 나타내는 방법의 수
            for(int i = 1; i<=3; i++) {
                ans += dp[n][i];
                ans %= div;
            }
            System.out.println(ans);
        }
    }
}