1로 만들기 - 1463

문제

풀이

import java.util.Scanner;

// 1로 만들기 - S3
public class ex1463 {
    static int answer=0;

    public static int solution(int x){
        // 1이 되는 경우의 수를 구해야한다.
        // 재귀 혹은 dp로 푸는 문제

        //dp[i] = 정수가 i를 1로 만들때 연산을 하는 횟수의 최솟값
        int dp[] = new int[x + 1];

        dp[0]=dp[1]=0;

        for(int i=2; i<=x; i++){
            dp[i]=dp[i-1]+1; //1을 뺀경우 : a
            if(i%2==0) dp[i]=Math.min(dp[i],dp[i/2]+1); // a와 2로 나눈값 중 최솟값 : b
            if(i%3==0) dp[i]=Math.min(dp[i],dp[i/3]+1); // b와 3으로 나눈값 중 최솟값
        }
        return dp[x];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        System.out.println(solution(n));

    }
}

우선 각 경우에 맞는 최솟값을 구하는 문제이다. 보자마자 재귀(DFS,BFS) 혹은 DP로 푸는 문제임을 알아야한다.

지금 내가 풀이한 방식은 DP 동적프로그래밍 방식이다.

DP 문제를 풀 땐 3가지 단계를 생각한다.
1. 테이블 정의
2. 점화식 찾기
3. 초기값 정하기

문제에 적용해보자.

1. 테이블 정의

D[i] = 정수가 i를 1로 만들때 연산을 하는 횟수의 최솟값

2. 점화식 찾기

D[12] = ?
3으로 나누거나 (D[12] = D[4] + 1) = (D[k] = D[k/3] + 1)
2로 나누거나 (D[12] = D[6] + 1) = (D[k] = D[k/2] + 1)
1을 빼거나 (D[12]=D[11]+1) = (D[k] = D[k-1] + 1)
-> D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)
-> D[k] = min(D[k/3] + 1, D[k/2] + 1, D[k-1] + 1)

즉,
-> D[i] = min(3으로 나눌 때, 2로 나눌 때, 1을 뺄 때)

3. 초기값 정의하기

D[0] = D[1] = 0