[backjoon_15990] 1,2,3 더하기 5(Java)

문제링크

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

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

문제설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

제한사항

제한시간	메모리제한
1초	512MB

*출처 : https://www.acmicpc.net/

문제풀이

DP를 사용하여 해결하면 문제를 해결하였다. 

D(n)을 n을 1,2,3으로 만드는 방법의 수라고 하자. 그러면 D(n)을 점화식으로 표현해주기 위해 끝에 무엇이 올 수 있는지 생각해보면 1과 2와 3이 올 수 있다. 따라서 위 세가지 경우를 계산해주고 더해주면 D(n)에 대한 점화식이 완성된다.

 

끝이 1이 올때는 1을 제외한 n-1에 대한 값이므로 D(n-1)이 된다.

2가 온 경우 앞의 값은 n-2이므로 D(n-2)이다.

3이 앞에 온 경우 앞의 값은 n-3 이므로 D(n-3)이다.

따라서 D(n) = D(n-1) + D(n-2) + D(n-3)이다.

 

그런데 위 점화식을 그대로 활용하면 안된다. 조건에서 연속된 숫자가 오면 안된다는 조건이 있기 때문이다.

따라서 맨 앞에 1이 오는 경우인 D(n-1)의 앞에 오는 숫자까지 고려해 주어야한다. 맨 뒤에 1이 오면 앞에 올 수 있는 숫자는 2와 3이다.

2가 오는 경우에는 1과 3이 올 수 있을 것이다.

3이 오는 경우에는 1과 2가 올 수 있다.

 

따라서 위 조건에서 현재 사용하고 있는 숫자까지 고려하여 알고리즘을 해결하면 된다.

예를 들어 D(n-1)의 경우  앞에 1,2,3 중 1을 제외한 2,3이 온 경우로 쪼개어 준다. 앞에 온 수 까지 고려하여 작성을 해주면 

D(n-1) = D(n-1,2) + D(n-1,3)이 된다. (맨 뒤 숫자가 1일 때이므로 그 앞에는 2 또는 3만 올 수 있다.)

 

따라서 최종적으로 점화식은

D(n) = D(n,1) + D(n,2) + D(n,3)

= D(n-1,2) + D(n-1,3) + D(n-2,1) + D(n-2,3) + D(n-3,1) + D(n-3,2)

이 된다.

 

        if(now == 1){
            findOne = (recursive(num - 1, 2) + recursive(num - 1, 3))%1000000009L;
        }
        else if(now == 2){
            findTwo = (recursive(num-2,1) + recursive(num-2, 3))%1000000009L;
        }
        else if(now == 3){
            findThree = (recursive(num-3,1) + recursive(num-3,2))%1000000009L;
        }
        return result[num][now] = (findOne + findTwo + findThree) %1000000009L;

위 점화식을 코드로 구현하면 위와 같다.  now가 현재 맨 뒤에 값이고 해당 값에 따라 recursive를 수행한다. 

%연산을 넣어준 이유는 나머지연산은 끝에만 해주면 언제든지 붙여도 상관이 없으므로, integer의 max값을 고려하여 %연산을 붙여 주었다. 그런데 조금 찜찜하여 그냥 long으로 다 바꾸어주었다.

        if(num == now)
            return 1;
        if(num < now)
            return 0;

종료되는 경우도 고려해보면  현재의 값과 현재 맨 뒤에 넣어주는 값이 일치하는 경우이다. 따라서 해당 경우에는 1을 넣어주고 뒤에 추가하는 값이 만약 더 커지는 경우에는 0을 넣어주면 된다.

구현코드

import java.util.Scanner;

public class Main {
    static long[][] result = new long[100001][4];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- != 0) {
            int num = sc.nextInt();
            System.out.println((recursive(num,1) + recursive(num,2) + recursive(num,3))%1000000009L);
        }
    }

    public static long recursive(int num, int now) {
        if(num == now)
            return 1;
        if(num < now)
            return 0;
        if(result[num][now] != 0)
            return result[num][now];

        long findOne = 0;
        long findTwo = 0;
        long findThree = 0;
        if(now == 1){
            findOne = (recursive(num - 1, 2) + recursive(num - 1, 3))%1000000009L;
        }
        else if(now == 2){
            findTwo = (recursive(num-2,1) + recursive(num-2, 3))%1000000009L;
        }
        else if(now == 3){
            findThree = (recursive(num-3,1) + recursive(num-3,2))%1000000009L;
        }
        return result[num][now] = (findOne + findTwo + findThree) %1000000009L;
    }
}

 

시간복잡도

문제의 수는 n개 이다.( n의 최대 - 100000)

하나의 문제를 푸는데 걸리는 시간은 덧셈과 나머지 연산이므로 1이다.

따라서 시간복잡도는 O(n)이다.