[백준] 9095번 1, 2, 3 더하기(DP)

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q9095.java

n이 주어질 때, 1과 2와 3을 이용해서 n을 만들 수 있는 경우의 수를 출력하여라.
더하는 순서에 따라 다른 가지수로 인정한다. 예를들어 1+2와 2+1은 다른 가지수이다.
n의 최대값은 11까지 주어진다.

처음 생각

이전에는 재귀를 통한 DFS 완전 탐색을 통해 문제를 풀었었다. [백준] 9095번 1, 2, 3 더하기 이번에는 풀고보니 DP로 푼걸로 봐서 이전 보다는 풀이 접근이 좋아진것 같다는 생각이 든다.

▶ 이전에 풀었던 완전탐색의 경우는 N의 크기가 커질경우 스택 초과 에러나 시간 초과를 받을 수도 있지만 DP는 O(N)으로 접근이 가능하기 때문에 그럴 문제가 없을 것이다.

다음 생각

DP적인 접근은 우선 쪼개서 생각하는 것이다. 따라서 주어진 1,2,3으로 쪼개보자.

▶ 1을 만들 수 있는 경우는 (1) 1개이다. 즉, arr[1] = 1

▶ 2을 만들 수 있는 경우는 (1+1) (2) 2개이다. 즉, arr[2] = 2

▶ 3을 만들 수 있는 경우는 (1+1+1) (2+1) (1+2) (3) 4개이다. 즉, arr[3] = 4

다다음 생각

N이 최대 11이므로 크기가 11인 배열을 미리 만들어 놓은 후, 작게 쪼갰을 경우 나오는 값을 위의 값으로 미리 넣어 주었다.

다다다음 생각

미리 값을 넣어준 후 반복문의 초기값을 4부터 주어진 n까지 진행을 한다. 만약 n이 4보다 작다면 반복문이 실행되지 않을 것이다. 4보다 큰 i에 대해서 arr[i]는 다음과 같이 구할 수 있다.

▶ i-1 값에서 +1 을 하면 i를 만들 수 있다. arr[i] = arr[i-1]

▶ i-2 값에서 +2 을 하면 i를 만들 수 있다. arr[i] = arr[i-2]+arr[i-1]

▶ i-3 값에서 +3 을 하면 i를 만들 수 있다. arr[i] = arr[i-3]+arr[i-2]+arr[i-1]

▶ 1개의 예로 살펴보자면 arr[4]의 경우는 arr[3]+arr[2]+arr[1]이 될 것이다. 이중 arr[3]을 봐보자. 3을 만들 수 있는 경우의 수는 4가지 인것을 위에서 살펴보았다. 이 3에서는 +1을 해서만 4를 만들 수 있다. 따라서 3의 만들 때의 가지수인 (1+1+1) (2+1) (1+2) (3) 에서 각 각의 경우에 +1을 한 (1+1+1+1) (2+1+1) (1+2+1) (3+1)가 4를 만들 수 있는 경우이므로, arr[3]에서의 변화는 없다. 4를 만들 경우 arr[2]와 arr[1]의 경우도 마찬가지이다.

다다다다음 생각

구하고자하는 수 n까지 반복문이 돌았다면 arr[n]을 통해 답을 출력하였다.

방안

1) Java 풀이

package baekjoon.q1000;
 
import java.io.IOException;
import java.util.Scanner;
 
public class Q9095 {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            int[] arr = new int[12];
            // 1
            arr[1] = 1;
            // 1+1,2
            arr[2] = 2;
            // 1+1+1, 1+2, 2+1, 3
            arr[3] = 4;
            for (int j = 4; j <= t; j++)
                arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3];
            System.out.println(arr[t]);
        }
    }
}
 

2) Python 풀이

tc = int(input())
for i in range(tc):
    n = int(input())
    a =[0 for x in range(12)]
    a[1]=1
    a[2]=2
    a[3]=1+2+1
    for j in range(4,n+1):
        a[j] = a[j-1]+a[j-2]+a[j-3]
    print(a[n])