[BOJ/DP] 백준 1463 - 1로 만들기 / 12852 - 1로 만들기 2 (Java)

1463 - 1로 만들기

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

 

문제

<정수 X에 사용할 수 있는 연산 3가지>
1. 3으로 나누어 떨어짐 -> /3
2. 2로 나누어 떨어짐 -> /2
3. -1 

=> 정수 N이 주어졌을 때, 연산 세 개 적절히 사용해서 1을 만들려고 함
-> 연산을 사용하는 횟수의 최솟값

입력: $10^6$ >= 자연수 N >= 1
출력: 연산을 하는 횟수의 쵯솟값

---

풀이

• `dp[i]`: 숫자 i -> 1로 만들기 위한 최소 연산 횟수
• dp[0] = dp[1] = 0

=> 항상 가능한 경우: i - 1 -> 1 

i - 1까지 최소 연산 횟수 구해져 있음 -> + 해서 i까지 도달하는 데 필요한 연산 수 계산

 

나눠떨어질 때 더 짧은 경로 O -> 최소 연산 횟수로 덮어씀

`dp[i] = dp[i / 2] + 1`, `dp[i] = dp[i / 3] + 1` => 어떤 연산이든, 그 연산 자체가 1회 추가

---

코드

import java.io.*;

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

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

        int[] dp = new int[N + 1];
        dp[0] = dp[1] = 0;

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

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

---

12852 - 1로 만들기 2

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

문제

<정수 X에 사용할 수 있는 연산 3가지>
1. 3으로 나누어 떨어짐 -> /3
2. 2로 나누어 떨어짐 -> /2
3. -1 

=> 정수 N이 주어졌을 때, 연산 세 개 적절히 사용해서 1을 만들려고 함
-> 연산을 사용하는 횟수의 최솟값

입력: $10^6$ >= 자연수 N >= 1
출력
첫째 줄: 연산을 하는 횟수의 쵯솟값
둘째 줄: N을 1로 만드는 방법에 포함되어 있는 수 (공백 구분)

---

풀이

• `dp[i]`: 숫자 i -> 1로 만들기 위한 최소 연산 횟수
• `prev[i]`: i에 도달하기 직전에 있던 숫자
  • 경로 추적(i 만들기 직전 수)
• dp[0] = dp[1] = 0

=> 항상 가능한 경우: i - 1 -> 1 

i - 1까지 최소 연산 횟수 구해져 있음 -> + 해서 i까지 도달하는 데 필요한 연산 수 계산

 

나눠떨어질 때 더 짧은 경로 O -> 최소 연산 횟수로 덮어씀

`dp[i] = dp[i / 2] + 1`, `dp[i] = dp[i / 3] + 1` => 어떤 연산이든, 그 연산 자체가 1회 추가

---

예시

N = 10

dp[1] = dp[1] = 0 

• i = 2 / dp[1] + 1 = 1
  • 2로 나눠 떨어짐 -> dp[1] + 1 =1  => 같음
  • dp[2] = 1, prev[2] = 1
• i = 3 / dp[2] + 1 = 2
  • 3으로 나눠 떨어짐 -> dp[1] + 1 = 1 => 같음
  • dp[3] = 1, prev[3] = 1
• i = 4/ dp[3] + 1 = 2
  • 2로 나눠 떨어짐 -> dp[2] + 1 = 2 => 같음
  • dp[4] = 2, prev[4] = 3
• i = 5 / dp[4] + 1 = 3
  • dp[5] = 3, prev[5] = 4
• i = 6/ dp[5] + 1 = 4
  • 2로 나눠 떨어짐 -> dp[3] + 1 = 2 => 더 작음
  • dp[6] = 2, prev[6] = 3
• i = 7 / dp[6] + 1 = 3
  • dp[7] = 3, prev[7] = 6
• i = 8 / dp[7] + 1 = 4
  • 2로 나눠 떨어짐 -> dp[4] + 1 = 3 => 더 작음
  • dp[8] = 3, prev[8] = 4
• i = 9 / dp[8] + 1 = 4
  • 3으로 나눠 떨어짐 -> dp[3] + 1 = 2
  • dp[9] = 2, prev[9] = 3
• i = 10 / dp[9] + 1 = 3
  • 2로 나눠 떨어짐 -> dp[5] + 1 = 4 => 더 큼
  • dp[10] = 3, prev[10] = 9

 

=> 1 -> 3 -> 9 -> 10

• dp[1] = 0
• dp[3] = dp[1] + 1
• dp[9] = dp[3] + 1
• dp[10] = dp[9] + 1

---

코드

import java.io.*;

// 1로 만들기 2
public class boj_12852 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        int[] dp = new int[N + 1];
        int[] prev = new int[N + 1];
        dp[0] = dp[1] = 0;

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;
            prev[i] = i - 1;

            if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
                dp[i] = dp[i / 2] + 1;
                prev[i] = i / 2;
            }
            if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
                dp[i] = dp[i / 3] + 1;
                prev[i] = i / 3;
            }
        }

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

        while (N > 0) {
            sb.append(N + " ");
            N = prev[N];
        }

        System.out.println(sb);
    }
}