[백준(Baekjoon)] 1463. 1로 만들기 (java, 동적계획법(DP))

안녕하세요. 오늘은 백준의 1463. 1로 만들기 문제를 풀어보겠습니다.

---

1. 문제 링크

https://www.acmicpc.net/problem/1463

2. 문제 풀이

이전에 풀었던 dp문제들과 마찬가지로, 2부터 쭉쭉 나열해본 결과 규칙을 찾을 수 있었습니다.

X	정답	정답 도출 방법
2	1	1*2 = 2
3	1	1*3 = 3
4	2	122 = 4
5	3	(5-1) -> 4, (X = 4일때 결과) + 1
6	1	123 = 6
7	2	(7-1) -> 6, (X = 6일때 결과) + 1
8	3	122*2 = 8
9	2	133 = 9
10	3	(10-1) -> 9, (10-2) -> 8
11	4	(11-1) -> 10, (11-2) -> 9
12	2	122*3 = 12
13	3	(13-1) -> 12, (13-2) -> 11
14	3	(14-1) -> 13, (14-2) -> 12, 14/2 -> 7
15	4	15/3 -> 5, (15-1) -> 14, (15-2) -> 13

위의 표처럼 구하려는 x가 2로 나뉘어지는지, 3으로 나뉘어지는지, 둘 다 나뉘어지지 않는다면 1을 빼주고 결과값을 확인하면 됩니다.
이를 점화식으로 나타낸다면 아래와 같습니다.

one = (만약 3으로 나뉘어진다면) dp[x/3]+1
two = (만약 2로 나뉘어진다면) dp[x/2]+1
three = dp[x-1] + 1
result = (one, two, three) 중 최소값

3. 전체 코드

import java.io.*;

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

        dp[1] = 0;

        for (int i = 2; i <= x; i++) {
            int tmp = i - 1;

            if (i % 2 == 0)
                tmp = Math.min(tmp, dp[i / 2] + 1);

            if (i % 3 == 0)
                tmp = Math.min(tmp, dp[i / 3] + 1);

            tmp = Math.min(tmp, dp[i - 1] + 1);

            dp[i] = tmp;
        }

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