[알고리즘] 1로 만들기 - 백준

문제

1463번: 1로 만들기

풀이 - java

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

public class Q1463 {
    public static void main(String[] args) throws IOException {
        int n = input();
        output(n);
    }

    static int input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        return Integer.parseInt(br.readLine());
    }

    static void output(int n) {
        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]);
    }
}

dp를 활용해서 문제를 풀었다.

정수 x에 활용할 수 있는 연산을 볼 때

1. 3으로 나누어 떨어진다면 3으로 나눈다. → 그러면 해당 값을 3으로 나눈 dp의 값에서 연산을 한 번만 더하면 해당 값이 나오게 된다.
2. 2로 나누어 떨어진다면 2로 나눈다. → 그러면 해당 값을 2로 나눈 dp의 값에서 연산을 한 번만 더하면 해당 값이 나오게 된다.
3. 1을 뺀다 → 그러면 해당 값에서 1을 뺀 dp의 값에서 연산을 한 번만 더하면 해당 값이 나오게 된다.

그렇게 생각하고 dp의 값을 채워넣어가는 방식으로 문제를 해결하였다.

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

모든 연산의 최종 값은 1이기 때문에 dp의 0번째 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);
}

앞에서 말한 대로 연산의 경우의 수는 3가지 이고 1번과 2번이 안될 경우 무조건 3번 연산을 수행하기 때문에, 일단 해당 3번 연산을 수행한 것으로 dp의 값을 초기화 한다.

이때 1번 연산과 2번 연산을 했을 경우의 연산값과 비교하여 최솟값을 해당 dp의 값으로 저장한다.

그러면 이전의 값들을 계속 dp에 저장이 되어있기 때문에, 중복적인 연산을 수행하지 않고 최소 연산값을 얻을 수 있다.

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

입력값과 인덱스를 맞춰서 배열을 만들었기 때문에 n번째 인덱스 값을 출력하면 해당 숫자의 최소 연산값을 알 수 있다.