[백준] 1463번 1로 만들기

1. 문제

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

주어진 정수 N에 대해 다음 세 가지 연산만 사용하여 N을 1로 만들 때, 최소 연산 횟수를 구하는 문제이다.

1. N이 3으로 나누어떨어지면, N = N / 3
2. N이 2로 나누어떨어지면, N = N / 2
3. N에서 1을 뺀다, N = N - 1

2. 풀이

📝 1차 시도

dp 배열을 활용하여 각 수 x를 1로 만들기 위한 최소 연산 횟수를 기록했다. dp[x]는 x를 1로 만들기 위한 최소 연산 횟수를 의미한다.

1️⃣ 초기값 설정

• dp[1] = 0
  1은 이미 1이기 때문에 연산이 필요하지 않음

2️⃣ 점화식

• x가 3으로 나누어떨어지면
  dp[x] = Math.min(dp[x - 1] + 1, dp[x / 3] + 1)

• x가 2로 나누어떨어지면
  dp[x] = Math.min(dp[x - 1] + 1, dp[x / 2] + 1)

• 그 외의 경우
  dp[x] = dp[x - 1] + 1

3️⃣ 예시 풀이 과정

아래는 x = 6까지의 연산 과정이다.

• x = 1 -> dp[1] = 0
• x = 2 -> dp[2] = dp[1] + 1 = 1
• x = 3 -> dp[3] = 1
• x = 4 -> dp[4] = min(dp[3] + 1, dp[2] + 1) = 2
• x = 5 -> dp[5] = dp[4] + 1 = 3
• x = 6 -> dp[6] = min(dp[5] + 1, dp[3] + 1) = 2

🔑 코드
아래는 Java로 구현한 코드이다.

import java.util.*;
import java.io.*;

public class Main {
    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[1] = 0;
        for (int i=2; i<=n; i++) {
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i-1] + 1, dp[i/3] + 1);
            else if (i % 2 == 0)
                dp[i] = Math.min(dp[i-1] + 1, dp[i/2] + 1);
            else
                dp[i] = dp[i-1] + 1;
        }
        System.out.println(dp[n]);
    }
}

=> 틀림

❌ 문제점

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

if-else로 나누어 처리하다 보니 3과 2 모두로 나누어떨어지는 경우를 고려하지 못했다. 3과 2 모두로 나누어지는 경우, 두 경로를 모두 시도해보고, 연산 횟수가 더 적은 방법을 선택해야 한다.

🛠️ 2차 시도

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);
}

먼저 1을 빼는 경우를 고려하고, 이후 2로 나누어떨어지는지 확인한 뒤, dp[i/2] + 1과 비교하여 최솟값을 선택한다. 마찬가지로 3으로 나누어떨어지는 경우를 확인하고, dp[i/3] + 1과 비교해 최솟값을 선택한다.

3. 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    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[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]);
    }
}