[알고리즘 PS(DP)] (백준 1463) 1로 만들기

백준 1로 만들기 는 solved.ac 기준 Tier : Silver3

이 문제는 DP 문제로 분류되며 DP 문제중 쉬운 편에 속한다.

DP 문제의 핵심은 큰 문제를 작은 문제로 나누기 이며, 해당 문제에도 적용하여 문제를 풀어야 한다.

큰 문제를 작은 문제로 나누기 위해서는 문제에 보이는 일정한 규칙을 찾아 점화식으로 도출하는 과정이 필수적이다.

문제

 

입출력

 

 

문제 해결 과정

 

1로 만들기 문제는 정수 x를 입력 받고 x가 1이되기 까지 최단 횟수를 구하는 것이다.

아무렇게나 1로 만드는 것이 아니라 다음과 같은 기준이 존재한다.

 

• x가 3으로 나누어 떨어지면 3으로 나눈다.
• x가 2로 나누어 떨어지면 2로 나눈다.
• x에 1을 뺀다.

이를 기준을 문제를 작게 만들어보자.

문제를 작게하는 방법

문제를 작게 만들기 위해서는 큰 문제를 정의하고 작은 문제로 나누는 생각에서 시작한다.

 

해당 문제의 풀이 식을 d(n) 이라고 했을 때, d(n) = 입력 n을 1로 만드는 최소 횟수 라고 정의할 수 있다.

 

이제 저 값에 위에서 말한 1로 만드는 기준을 적용시켜보자.

• x가 3으로 나누어 떨어지면 3으로 나눈다.

  x/3 으로 만들기 위한 경우의 수 1번 + x/3 을 1로 만드는 경우의 수 x/3

• x가 2로 나누어 떨어지면 2로 나눈다.

  x/3 으로 만들기 위한 경우의 수 1번 + x/3 을 1로 만드는 경우의 수 x/3

• x에 1을 뺀다.

  x-1 을 1로 만드는 경우의 수 x-1번

위의 식에 대한 최솟값을 구하는 것이므로
d[n] = d[n/3] + 1, d[n/2] + 1, d[n-1]의 최솟값을 구하면 된다.

점화식

위의 해결 과정을 점화식으로 만들면 다음과 같다.
d[n] = min(d[n/3] + 1, d[n/2] + 1, d[n-1])

소스 코드

package stage.stage11_DynamicPrograming;

import java.util.Scanner;

import java.io.*;

public class Prob02_MakeOne {

    static int[] memo;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        memo = new int[n+1];

        bw.write(dp(n) + "\n");

        bw.flush();

        bw.close();

    }

    private static int dp(int n){

        if(n == 1) return 0; // minimum case

        if(memo[n] > 0) return memo[n]; // duplication checker

        memo[n] = dp(n-1) + 1; // this location is important.

        if(n % 2 == 0){

            int temp = dp(n/2) + 1;

            if(memo[n] > temp) memo[n] = temp;

        }
        else if(n % 3 == 0){

            int temp = dp(n/3) + 1;

            if(memo[n] > temp) memo[n] = temp;

        }

        return memo[n];
    }
}