✨ 문제

1463번 - 1로 만들기

✨ 풀이

📍 알고리즘

DP(Dynamic Programming) 알고리즘

📍 설명

• 주어진 정수에 사용할 수 있는 연산
  👉🏻 3으로 나누기, 2로 나누기, 1로 빼기로 총 3가지가 존재한다.
• 1은 1이 되기 위해 0번의 연산이 필요하다.
• 2는 1이 되기 위해 2/2나 2-1로 1번의 연산이 필요하다.
• 3은 1이 되기 위해 3/3으로 1번의 연산이 필요하다.
  👉🏻 숫자 N이 최소 연산 횟수로 1이 되기 위해서는 1, 2, 3, ... N-1이 1이 되기 위한 최소 연산 횟수를 구해 그것을 이용하면 된다.

✔️ 정리하자면, dp 알고리즘에서는 결과가 같은 작은 문제가 반복되어 그 작은 문제의 해법을 미리 저장해놓고 다시 계산하지 않도록 하는데, 여기서는 그 작은 문제가 1~N-1의 1이 되기 위한 최소 연산 횟수이다. "최소" 연산 횟수이므로 Math.min을 사용해 최소 연산 횟수를 구할 수 있도록 했다. 이러한 형태가 잡히면 각자의 풀이는 다양해질 수 있는데, 따로 함수를 만들지는 않고 for문을 이용해 풀었다.

✨ 최종 코드

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

public class Main {
    static int N;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        dp[1] = 0;

        for(int i = 2; i < N+1; i++) {
            if(i % 6 == 0){
                dp[i] = Math.min(dp[i/3], dp[i/2]) + 1;
            } else if(i % 3 == 0){
                dp[i] = Math.min(dp[i/3], dp[i-1]) + 1;
            } else if(i % 2 == 0){
                dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;
            } else{
                dp[i] = dp[i-1] + 1;
            }
        }

        System.out.println(dp[N]);
    }
}

👩🏻‍💻 후기 및 다짐

이번주 cs 스터디에서 알고리즘 중 dp를 공부하여 복습 차원으로 풀어본 문제이다. dp 알고리즘 문제를 아직 많이 못 풀어봐서 앞으로 계속해서 풀어볼 예정이다. 코드를 작성하는 것은 오래 걸리지 않는데((생각을 오래 하니까..)), 작은 문제를 뽑아내는 연습을 더 해야겠다!! 그리고 아무래도 이 문제를 dp로 풀어야 한다는 것을 알고 푸니까 더 쉽게 푼 것 같다. 이제 그냥 문제를 풀 때도 dp로 풀 수 있나 점검해봐야지❗️
다음에는 1003 피보나치 수열 문제를 풀어볼 예정이다.