백준 1463번 1로 만들기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class MakeOne {
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        System.out.println(cal(N));
    }
    public static int cal(int n){
        if(n==1){
            return 0;
        }
        if(dp[n]==0){
            if(n%6==0){
                dp[n] = Math.min(cal(n/3)+1,Math.min(cal(n/2)+1,cal(n-1)+1));
            }
            else if(n%3==0){
                dp[n] = Math.min(cal(n/3)+1,cal(n-1)+1);
            }
            else if(n%2==0){
                dp[n] = Math.min(cal(n/2)+1,cal(n-1)+1);
            }
            else {
                dp[n] = cal(n-1)+1;
            }
        }
        return dp[n];
    }
}

풀이방법

📢이 문제에서는 할 수 있는 연산이 세가지로 나와있다.

• 3으로 나누어 떨어질 경우 3으로 나누기
• 2로 나누어 떨어질 경우 2로 나누기
• 1빼기

이 연산들중에는 겹치는 연산이 있기 때문에 경우의 따라 해당 연산들 중에 나오는 최소값을 구해야한다.

1. 3으로 나누어 떨어질 경우에, 3으로 나누거나, 1을 빼거나 두가지 연산 중에 최솟값을 고른다.
2. 2로 나누어 떨어질 경우에 2로 나누거나 , 1을 빼거나 두가지 연산중에 최솟값을 고른다.
3. 3,2로 안나누어 진다면 1을 뺀다.

👉단 이때 6의 배수에서는 3과 2가 동시에 나누어 떨어지므로, 3,2로 나누거나, 1을 빼거나 세가지 연산중에 최솟값을 고르도록 한다.

후기

DP에 대해 전혀 감을 잡지 못하고 있는것 같다.
내가 사용하는 방식은 top-down 방식인데 bottom-up 방식도 함께 사용해 봐야겠다.