[백준 15988][Silver 2] - 1, 2, 3 더하기 3(JAVA)

 

문제 링크

---

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

 

문제

---

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

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

 

입력

---

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

 

출력

---

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

 

문제 해석

---

문제의 조건을 나열하면 다음과 같다.

• 주어진 수를 표현한는 방법은 1, 2, 3의 조합이다.
• N은 최대 1,000,000이다.

 

1,2,3를 N개 이하로 사용하여 숫자 N을 만들었을 때 가능한 모든 경우의 수를 구하면 되는 문제이다. 경우의 수를 찾는 알고리즘은 대표적으로 완전탐색, dp 등이 있다. 

 

완전탐색으로 풀릴까??

---

경우의 수를 찾는 가장 쉬운 방법은 모든 경우의 수를 다 찾는 완전탐색이다.  만약 완전 탐색인 조합으로 모든 경우를 찾는다면 시간 복잡도는 다음과 같다.

(1를 사용하는 경우) * (2를 사용하는 경우) * (3을 사용하는 경우)
= 2^n * 2^n * 2*n
= 2^(n+3)
≒ 2^n

 

물론 2는 최대 n/2개, 3은 최대 n/3개를 쓰므로 해당 식보다 더 작게 나오겠지만 N은 최대 1,000,000이기 때문에 정밀하게 수를 조정해도 2^1000000 의 수는 1초인 1억보다 매우매우 큰 수이기 때문에 완전탐색인 조합으로 풀게되면 시간초과가 날 것이다. 우린 다른 방법을 찾아야한다.

 

 

DP로 풀릴까??

---

다음으로 경우의 수를 찾는 방법인 DP를 생각해보자. DP를 사용하기 위해선 점화식, 즉 일정한 규칙을 찾아야한다. Bottom-up 방식(재귀)보다 Top-down 방식(반복문)이 시간 복잡도가 훨신 낮으므로 Top-down 방식인 생각을 하기위해 1부터 5까지의 5의 경우의 수까지 구해서 규칙을 찾아보자.

1) 1을 만들 수 있는경우
= (1을 1개 사용함 + 0을 만드는 경우의 수)
= 1
= 1가지

2) 2를 만드는 경우의 수
=(1를 1개 사용함 + 1을 만드는 경우의 수)  + (2를 1개 사용함 + 0을 만드는 경우의수)
= 1 + 1
= 2가지

3) 3을 만들 수 있는경우
=(1를 1개 사용함 + 2를 만드는 경우의 수)  + (2를 1개 사용함 + 1을 만드는 경우의 수) +
(3을 1개 사용함 + 0을 만드는 경우의 수)
= 2 + 1 + 1
= 4가지

4) 4를 만들 수 있는경우
=(1를 1개 사용함 + 3을 만드는 경우의 수)  + (2를 1개 사용함 + 2를 만드는 경우의 수) +
(3을 1개 사용함 + 1을 만드는 경우의 수)
= 1 + 2 + 4
= 7가지

5) 5를 만들 수 있는경우
=(1를 1개 사용함 + 4를 만드는 경우의 수)  + (2를 1개 사용함 + 3을 만드는 경우의 수) +
(3을 1개 사용함 + 2를 만드는 경우의 수)
= 2 + 4 + 7
= 11가지

 

규칙이 보이는가?? 예를들어 1을 1개 사용하려면 N-1을 만드는 경우의 수를 구하면 되고 2를 1개 사용하려면 N-2를 만드는 경우의 수를 구하면 된다. 그러므로 점화식은 다음과 같다.

숫자 N을 만드는 경우의 수
= 숫자 N-1를 만드는 경우의 수 + 숫자 N-2를 만드는 경우의 수 + 숫자 N-3를 만드는 경우의 수

dp[N] =dp[N-1] + dp[N-2] + dp[N-3]

 

시간복잡도를 구해보자

---

DP방식으로 문제를 해결하려고 하면 점화식인 dp[N] =dp[N-1] + dp[N-2] + dp[N-3]에 따라 해결해야 한다. 이를 코드로 옮기면 다음과 같다,.

for(i=3;i<=N;i++){
	dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
}

 for문 1개로 해결할 수 있으므로 시간복잡도는 O(n)이다. 이때 N은 최대 1,000,000이므로 제한시간인 1초 이내로 할 수 있다.

 

경우의 수를 한번에 계산하자

---

주의해야할 점이 1가지 있는데 바로 테스트 케이스가 있다는 점이다. 즉 O(n)의 로직을 T번 반복할 수 있는데 만약 T가 1,00 이상이라면 1,000,00 * 100 = 1억이기 때문에 제한시간인 1초 이내로 풀리지 않을 수 있다.

 

 

그러므로 최대값인 1,000,000까지의 경우의 수를 미리 구해놓고 이후에 들어오는 테스트케이스의 숫자의 값의 경우의 수를 가져오면 시간복잡도가 T * O(N)이 아니라 T + O(N)이 되므로 T가 1억 미만이라면 제한시간인 1초 이내로 해결할 수 있다! 

 

코드

---

import java.io.*;

public class Main {
    final static int MOD = 1_000_000_009;
    final static int MAX = 1_000_000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));

        int[] dp = new int[MAX+1];

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

        for(int i=4;i<dp.length;i++){
            dp[i] = ((dp[i-1]%MOD) + (dp[i-2]%MOD))%MOD;
            dp[i] = ((dp[i]%MOD) + (dp[i-3]%MOD))%MOD;
        }

        int T = Integer.parseInt(br.readLine());

        for(int testcase=1;testcase<=T;testcase++){
            int n = Integer.parseInt(br.readLine());

            System.out.println(dp[n]);
        }
    }
}

 

 

실행 결과

---

제한시간인 1초안에 문제가 해결 되었다!

 

키워드

---

• 모든 경우의 수
  
  • 모든 경우의 수 말이 붙으면 완전탐색, DP의 가능성을 가지고 있다

 

팁

---

1. DP는 Bottom-up 보다 Top-down 방식이 시간복잡도 상 유리하므로 최소값부터 다음값으로 하나씩 늘려갔을 때의 규칙을 찾아보자.
2. 규칙을 모르겠으면 경우의 수를 5개를 직접 만들어 봐서 이전 값을 더하고 빼주어 점화식을 유추해보자