[JAVA] 백준 알고리즘 1463번 (1로 만들기)

문제

---

이번에 다뤄볼 문제는 1463번 문제 '1로 만들기'입니다.

1로 만들기 문제에서 연습해야 하는 key-point는 DP입니다.

 

DP(Dynamic Programing)는 이름때문에 어려워 하시는 분들이 많습니다.

그렇다고 해서 동적계획법에 대해 구글링하며 찾아보실 필요는 없습니다.

DP는 쉽게 말하면 어려운 또는 커다란 문제를 작은 문제들로 나눠서 풀이하겠다 인데요.

작은 문제들을 해결해서 메모해놓고 나중에 더 큰 문제를 해결하면서 같은 작은 문제를 만난다면

앞서 풀었던 작은 문제의 결과를 활용하는 방식입니다.

 

문제에서 주어진 1로 만들기의 경우 총 3가지의 연산방식이 있습니다.

3으로 나누기 / 2로 나누기 / 1 빼기

이 3개의 연산을 갖고 dp[]라는 메모장에 작은 문제부터 올라가며 해결하고 기록합니다.

 

우선 1을 만드는 것이 목적이기 때문에 0 이나 1이 입력될 경우 연산을 거칠 필요가 없습니다.

따라서  dp[0]과 dp[1]에는 각각 0을 세팅하겠습니다.

 

그리고 이제 0과 1은 해결하였으니 2부터 n까지 for문을 돌며 작은 문제들을 해결합니다.

 

예시를 통해 풀이해보겠습니다.

 

숫자 10이 입력됩니다.

그럼  dp[0] dp[1] 에는 각각 0이 세팅됩니다.

반복문에 진입합니다.

반복문에 진입했다는 얘기는 연산을 한번 수행한다는 의미이기 때문에

직전 dp값에 1을 더해줍니다. 따라서 dp[2]에는 dp[1]+1 즉 1이 저장됩니다.

그다음 2는 3으로 나누어 떨어지진 않지만 2로는 나누어 떨어집니다.

그럴 경우 해당 분기에서 dp[i] > dp[i / 2] + 1 조건을 타게 되는데

이 이유는 주어진 문제에서 최종 결과를 얻기위한 최소한의 연산 횟수를 얻기 위함이기 때문에 추가되는 조건입니다.

이후 위의 과정을 반복하며 목적지인 10까지 최소한의 연산을 구해가며 도달하는 방식으로 문제를 해결합니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

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

        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
                dp[i] = dp[i / 3] + 1;
            }
            if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
                dp[i] = dp[i / 2] + 1;
            }
        }

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

 

1463번: 1로 만들기