알고리즘 풀이 - 백준 9095(1,2,3 더하기, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

 

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제

이 문제를 완전 탐색(재귀)를 이용하여 풀 수도 있다. 그 방법은 여기를 참조

 

2. 풀이

 

이 문제는 DP로 해결 가능하다.

우선 두 가지 조건이 만족하는지 알아보자. 각 정수는 n으로 표기하여 이 자체가 변수로 하나의 State를 나타낸다.

정수 n을 1, 2, 3의 합으로 나타내는 방법은 아래와 같다.

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

즉, 작은 문제들인 n-3, n-2, n-1을 반복하여 사용하고 해당 최적 결과값이 그대로 사용되므로 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 한 번 세워보자. 아래와 같을 것이다.
정의 : dp[n] = n을 1, 2, 3의 합으로 나타내는 방법의 수

n 하나 만이 변수이므로 1차원의 배열을 통해 상태 저장이 가능할 것이다. 기저 상태와 점화식을 세워보자.

기저 상태는 n이 1, 2, 3의 경우일 것이다. n=1일 때는 1로 한 가지만 가능하며, 2는 1+1과 2의 2가지, 3은 1+1+1, 1+2, 2+1, 3의 4가지이다.
기저 상태 : dp[1] = 1, dp[2] = 2, dp[3] = 4

점화식은 아래와 같다.
점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(bottomUp(n));
        }
        
        br.close();
    }
    
    // Bottom-up 방식
    public static int bottomUp(int n){
        dp = new int[11];
        
        // 기저 상태는 1, 2, 3을 각각 나타내는 방법의 수
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        
        // 반복문을 통해 점화식을 구성하여 최소값을 채워나감
        for(int i=4; i <= n; i++){
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }
        return dp[n];
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i < T; i++){
            dp = new int[11];
            // 기저 상태는 1, 2, 3을 나타내는 방법의 수
            dp[1] = 1; dp[2] = 2; dp[3] = 4;
            int n = Integer.parseInt(br.readLine());
            System.out.println(topDown(n));
        }
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int n){
        if(dp[n] > 0) return dp[n];
        return dp[n] = topDown(n-3) + topDown(n-2) + topDown(n-1);
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.