[BOJ/Java] 1463. 1로 만들기

[BOJ/Java] 1463. 1로 만들기

1463번: 1로 만들기

---

문제 해석

이 문제는 주어진 수 𝑋X를 1로 만드는 데 필요한 최소 연산 횟수를 찾는다. 연산은 다음 세 가지 중 하나를 선택할 수 있다:

 

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

풀이 과정

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있다. 각 숫자 𝑖i에 대하여, 𝑖i를 1로 만드는 최소 연산 횟수를 dp[i] 배열에 저장한다. 점화식은 다음과 같다:

 

• 𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+1
• 𝑑𝑝[𝑖]=min⁡(𝑑𝑝[𝑖],𝑑𝑝[𝑖/3]+1) (만약 𝑖%3==0i%3==0)
• 𝑑𝑝[𝑖]=min⁡(𝑑𝑝[𝑖],𝑑𝑝[𝑖/2]+1) (만약 𝑖%2==0i%2==0)

코드

package edu.ssafy.im.BOJ.Silver.S3.No1463;

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int X = Integer.parseInt(br.readLine());
        
        int[] dp = new int[X+1];
        dp[1] = 0;  // 1을 1로 만드는 데 필요한 최소 연산 횟수는 0
        
        for (int i = 2; i <= X; i++) {
            dp[i] = dp[i-1] + 1;  // 연산 3: 1을 빼는 경우
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);  // 연산 1: 3으로 나누는 경우
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);  // 연산 2: 2로 나누는 경우
        }
        
        sb.append(dp[X]);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 𝑂(𝑁)이다. 여기서 𝑁은 입력으로 주어진 𝑋의 값이다. 각 숫자에 대해 세 가지 연산 중 최소 값을 계산하기 때문에, 동적 계획법을 통해 효율적으로 문제를 해결한다.

느낀점

동적 계획법을 사용하여 주어진 문제를 체계적으로 분해하고 해결하는 방법을 배우고, 이를 통해 문제를 해결하는 것은 매우 유익한 경험이었다. 본 문제처럼 간단한 점화식을 통해 복잡한 문제를 해결할 수 있다는 것을 알게 되었다.