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

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

1463번: 1로 만들기

---

문제 해석

이 문제는 주어진 수 N을 1로 만드는 최소 횟수를 구하는 문제다. 수행할 수 있는 연산은 세 가지로, N을 3으로 나누기, 2로 나누기, 또는 1을 빼는 연산이 있다. 주어진 N에 대해 세 가지 연산을 적절히 조합하여 1로 만드는 데 필요한 최소 연산 횟수를 찾는 것이 목표다.

풀이 과정

본 코드는 동적 계획법을 사용하여 문제를 해결한다. 배열 dp를 사용하여 각 숫자 i를 1로 만들기 위해 필요한 최소 연산 횟수를 저장한다. dp[i]는 i번째 숫자를 1로 만드는 데 필요한 최소 연산 횟수를 나타낸다.

 

1. 초기화: dp[1]은 0으로 설정한다. 1을 1로 만드는 데 필요한 연산은 없으므로 연산 횟수는 0이다.
2. 점화식 구성: 각 숫자 i에 대해, i가 1인 경우를 제외하고, 다음의 점화식을 사용한다:
   • dp[i] = dp[i-1] + 1: i에서 1을 빼는 연산.
   • if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1): i가 3으로 나누어떨어질 경우, i를 3으로 나누는 연산.
   • if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1): i가 2로 나누어떨어질 경우, i를 2로 나누는 연산.
   • 위 점화식을 사용하여, 각 i에 대해 세 가지 연산 중 최소값을 dp[i]에 저장한다.
3. 결과 출력: 계산된 dp[N]을 출력하여 주어진 N을 1로 만드는 데 필요한 최소 연산 횟수를 제시한다.

코드

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

import java.io.*;

public class Main {
    private static int N;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());  // 입력 받은 수 N
        dp = new int[N + 1];  // N+1 크기의 배열 생성

        dp[1] = 0;  // 1은 이미 1이므로 연산 필요 없음
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i-1] + 1;  // 1을 빼는 연산
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);  // 3으로 나누는 연산
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);  // 2로 나누는 연산
        }

        sb.append(dp[N]);  // 결과 값 StringBuilder에 추가
        bw.write(sb.toString());  // 결과 값 출력
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)이다. 각 숫자 i에 대해 세 가지 경우의 수를 확인하고 최소값을 구하는 연산을 수행한다. 그러나 각 i에 대해 일정한 수의 연산만 수행되므로, 시간 복잡도는 입력 크기 N에 선형적으로 비례한다.

느낀점

동적 계획법을 통해 복잡한 문제를 단순화시켜 해결할 수 있었다는 점이 매우 인상적이었다. 문제를 작은 단위로 나누어 각 단위의 최적해를 찾는 방식이 강력함을 다시 한번 느낄 수 있었다. 이러한 접근 방식은 다양한 최적화 문제에 활용 가능하여 알고리즘 설계에 있어 매우 중요한 기술이다.