백준 - 1463번(1로 만들기)

문제 출처: https://www.acmicpc.net/problem/1463

문제

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());

        int[] DP = new int[N + 1]; // DP 테이블

        for (int i = 2; i <= N; i++) {
            int min = 1 + DP[i - 1];
            if (i % 3 == 0 && 1 + DP[i / 3] < min) min = 1 + DP[i / 3];
            if (i % 2 == 0 && 1 + DP[i / 2] < min) min = 1 + DP[i / 2];

            DP[i] = min;
        }

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

}

• DP를 사용하여 풀 수 있는 문제였다.
• 각각의 단계에서 1을 뺐을 때의 연산 수, 3으로 나누어지는 경우 3으로 나눈 때의 연산 수, 2로 나누어지는 경우 2로 나눈 때의 연산 수 중 최솟값을 DP 테이블에 저장하여 진행하였다.