알고리즘 풀이 - 백준 1463(1로 만들기, DP)

 

관련글

 

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

 

 

1. 문제

 

문제 링크는 여기를 참조

 

 

간단하게 설명하여 1 ~ 1,000,000 까지 숫자 중 하나를 입력 받아 해당 숫자에서 1을 빼거나, 2 또는 3으로 나누는 작업을 반복하여 1이 되게 하려면 몇 번의 연산이 필요한지 구하는 문제이다.

 

 

2. 풀이

 

우선 이 문제는 DP로 풀 수 있다. DP로 풀 수 있는지 어떻게 알 수 있을까? 

DP인지 아닌지 확인하려면 우선 2가지 조건이 만족되는지를 알아야 한다. 그 조건은 다음과 같다.

1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)

 

예를 들어, 숫자 5를 1로 만들기 위해서는 아래와 같은 방법이 있을 것이다.

5 → 4(-1) → 3(-1) → 2(-1) → 1(-1)
5 → 4(-1) → 3(-1) → 1(/3)
5 → 4(-1) → 2(/2) → 1(/2)

 

이 때, 5를 1로 만들기 위해 거치는 과정이 여러 개 이지만 그 이전의 숫자들이 1이 되는 과정을 거쳐서 진행된다는 것을 알 수 있다. 따라서 다양한 방식으로 진행 시, 3을 1로 하거나 2를 1로 만드는 작업이 반복된다.

따라서 Overlapping Subproblems(겹치는 부분 문제) 가 적용될 수 있다.

 

또한, 5보다 작은 숫자를 1로 만들기 위한 연산 횟수 중 최소값이 현재 구하고자 하는 숫자를 1로 만드는데 필요한 연산 횟수에 그대로 사용될 수 있다.

따라서 Optimal Substructure(최적 부분 구조)가 적용될 수 있다.

 

저장할 배열을 만들어보자. 작은 문제의 결과값을 저장하기 위해 아래와 같이 문장화하여 좀 더 이해하기 쉽게 만들어보자.
dp[N] = N을 1로 만드는 최소 연산의 횟수

N이라는 숫자 하나가 변수이므로 저장할 배열은 1차원으로 구현될 수 있다.

 

이후로 기저 상태를 파악하고 점화식을 구현하여 재귀 / 반복을 통해 구현을 수행하면 된다.

점화식은 당연히 다음과 같을 것이다. 각각의 경우 중 최소값을 찾아내면 된다.
점화식 : dp[n] = min(dp[n/3], dp[n/2], dp[n-1]) + 1

답은 구할 수 없는 기저 상태는 무엇일까?
1로 만들기이므로 1을 1로 만드는 경우가 가장 작은 문제이다. 그러므로 dp[1] = 0으로 초기화한다.

 

 

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 X = Integer.parseInt(br.readLine());
        System.out.println(bottomUp(X));
        
        br.close();
    }
    
    // Bottom-up 방식
    public static int bottomUp(int X){
        dp = new int[X+1];
        
        // 기저 상태는 1을 1로 만드는 경우. 불 필요하지만 이해를 위해 추가
        dp[1] = 0;
        
        // 반복문을 통해 점화식을 구성하여 최소값을 채워나감
        for(int i=2; i <= X; i++){
            // 3으로 나눌 수 있다면
            int mod3 = i % 3 == 0 ? dp[i/3]+1 : Integer.MAX_VALUE;
            
            // 2로 나눌 수 있다면
            int mod2 = i % 2 == 0 ? dp[i/2]+1 : Integer.MAX_VALUE;
            
            // 그 중 작은 값으로 저장
            int min = Math.min(mod2, mod3);
            
            // 1로 뺀 경우에서 최소값으로 저장
            dp[i] = Math.min(dp[i-1]+1, min);
        }
        return dp[X];
    }
}

 

 

2) Top-Down 방식

Top-Down의 경우는 일반적인 경우처럼 만들면 시간 초과가 날 수 있어서 조금 변형해서 코드를 구현 해야 한다.

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int X = Integer.parseInt(br.readLine());
        System.out.println(topDown(X, 0));
        
        br.close();
    }
    
    // Top-Down 방식
    public static int topDown(int X, int count){
        // X가 2 미만이면 이전 계산으로 누적된 count를 반환
        if(X < 2) return count;
        
        // count는 최초에 0으로 전달되었으며 연산을 수행하며 1씩 추가하는 방식이다.
        // 1을 빼는 경우가 없다고 생각되는 경우, 2로 나누고 3으로 나눈 나머지를 뒤에 더하는 식이 포함되어 있음을 확인한다.
        return Math.min(topDown(X / 2, count+1+(X%2)), topDown(X / 3, count+1+(X%3)));
    }
}

 

보통 생각하는 방식이라면 아래와 같이 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 X = Integer.parseInt(br.readLine());
        
        dp = new int[X+1];
        System.out.println(topDown(X));
        
        br.close();
    }
    
    // Top-Down 방식
    public static int topDown(int X){
        if(X <= 2) return dp[X] = X-1; // 기저 상태
        if(dp[X] > 0) return dp[X];    // 이전 계산된 값 반환
        
        dp[X] = topDown(X-1) + 1;
        if(X % 3 == 0){
            int temp = topDown(X/3)+1;
            dp[X] = Math.min(dp[X], temp);
	    }
        if(X % 2 == 0){
            int temp = topDown(X/2)+1;
            dp[X] = Math.min(dp[X], temp);
        }
        return dp[X];
    }
}

 

 

감사합니다. 오류가 있으면 댓글 부탁드려요.