[백준/Java] 9095번 : 1, 2, 3 더하기

✏️ 문제 탐색

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

1, 2, 3의 합으로 N을 만드는 경우의 수를 구하는 문제이다.

✏️ 구현 아이디어

일단 각 경우의 수를 구해 보았다. 어떤 규칙이 보이는 것 같다.

 

n=1 : {1} 1개
n=2 : {11, 2}  2개
n=3 : {111, 12, 21, 3} 4개
n=4 : {1111, 112, 121, 211, 22, 13, 31} 7개

여기서 n=4를 앞에서 구한 n=1, n=2, n=3을 사용해 표현할 수 있을 것 같다.

표로 정리해서 점화식을 도출해보자.

 

N	방법의 수	케이스
1	1	1
2	2	1+1, 2
3	4	1+1+1, 1+2, 2+1, 3
4	7	( 1+1+1+1, 1+1+2, 1+2+1, 1+3 ), (2+1+1, 2+2), (3+1)
5	13	(1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+1+3, 1+2+1+1, 1+2+2, 1+3+1), (2+1+1+1, 2+1+2, 2+2+1, 2+3), (3+1+1, 3+2)

 

4 이상의 정수 N에서 N의 케이스는 아래와 같이 구성된다.

1) N-1 케이스에 1을 추가

2) N-2 케이스에 2를 추가

3) N-3 케이스에 3을 추가

 

예를 들어 N=4은 ( 1+1+1+1, 1+1+2, 1+2+1, 1+3 ), (2+1+1, 2+2), (3+1) 로 구성되어 있는데 이것은 다음과 같이 표현할 수 있다.

N=3 (1+1+1, 1+2, 2+1, 3) 의 각 경우에 1을 더하기

N=2 (1+1, 2) 의 각 경우에 2를 더하기

N=1 (1) 의 각 경우에 3을 더하기

 

이때, N의 케이스는 N-1, N-2, N-3 각각의 케이스에 1, 2, 3을 추가하기만 했으니까 갯수의 변화는 없다.

따라서 점화식은 if(4<=N) d[N] = d[N-1] + d[N-2] + d[N-3] 

✏️ 알고리즘

이전에 구한 답을 활용해서 다음 문제의 답을 구하는 식으로 해결할 수 있는 문제이다.

따라서 DP를 사용해서 풀 수 있다.

 

💡DP(Dynamic Programming)는 답을 도출할 때 전체 문제를 작은 단위로 나누어서 해결하는데,

그 부분 문제들이 반복적으로 나타나는 경우 사용할 수 있는 알고리즘이다. 

memoization을 사용해 이전 문제의 결과를 다음 문제를 풀 때 사용할 수 있다.

✏️ 시간 복잡도

DP는 모든 문제를 한 번씩만 해결하므로 전체 시간 복잡도는 O(N)이다.

n은 11보다 작은 양수이므로 제한 시간인 1초 안에 해결할 수 있다.

✏️ 코드 설계

1. memoization을 위한 배열 d[]를 선언한다.
2. 초기값으로 d[1], d[2], d[3]을 저장한다.
3. dp() 함수를 만든다.
   • 이미 d[]에 값이 들어있다면 그 수를 반환
   • 아직 값이 구해지지 않았다면 재귀 호출하여 d[n]값을 구하기
   • d[n] = dp(n-1) + dp(n-2) + dp(n-3)으로 구할 수 있다.
4. 각 테스트 케이스 마다 n값을 받아서 dp(n)을 실행시킨다.
5. 구해진 답을 출력한다.

✏️ 오답 노트

처음에는 N=4까지만 구해보고 점화식을 d[N] = d[N-1] + (N-1)로 도출했다.

규칙을 찾을 때는 시행 횟수를 적어도 5회 이상으로 잡아야겠다.

✏️ 정답 코드 1

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int[] d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        d = new int[11];
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;

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

        for(int i=0; i<T; i++){
            int N = Integer.parseInt(br.readLine());
            bw.write(dp(N) + "\n");
        }
        bw.close();
    }
    static int dp(int x){
        if(d[x] != 0) return d[x];
        return d[x] = dp(x-1) + dp(x-2) + dp(x-3);
    }
}

 

✏️ 정답 코드 2

N이 최대 10이므로 미리 dp값을 다 구해두고 d[n]만 출력하는 방법이다. 

재귀호출보다 12ms 빠르고 메모리도 약 1000kb 아낄 수 있다.

 

import java.io.*;

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

        int T = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4; i<11; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n] + "\n");
        }
        System.out.println(sb);

    }
}