[백준] [1463] 1로 만들기 (JAVA) (dp)

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

1463번: 1로 만들기

---

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.15 초 (하단 참고)

128 MB

278129

93963

59877

32.751%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

※ JAVA 코드 (1로 만들기)

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

public class Main {
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        dp = new int[10000001];
        System.out.println(dp(n));
    }

    public static int dp(int n) {
        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);
            }
        }

        return dp[n];
    }
}

---

※ 생각정리 (1로 만들기)

1. dp 문제를 풀기위해서는 생각하는 힘을 길러야한다.

2 . 피보나치 수열을 생각해보자

1, 1, 2, 3, 5, 8, 13, 21, 34 ......

n번째 수를 구한다고 하였을때 dp[n] = dp[n-2] + dp[n-1]과 같은 점화식을 세울 수 있다. 그렇다면 왜 이 문제를 풀기전에 이런 것을 설명하는 것이 궁금할 것이다.

이 문제 또한 임의의 숫자 n이 주어졌을 때 해당 숫자를 1로 만드는 과정에서 여러 숫자를 거치게 되고 해당 숫자 인덱스 위치의 배열에 그 숫자를 구하기 위한 최소값을 담아두면 빠르게 해결 할 수 있다. 이해가 안되신다면 다음 설명을 확인해주세요

우리는 1이라는 숫자를 1로 만들기 위해서는 0번의 횟수가 최소값이 되기에 dp[1] = 0 이라 할 수 있다.

그렇다면 2라는 숫자를 1로 만들기 위해서 즉, dp[2]? 두가지 경우의 수가 있다.

1) 2 -1 = 1

2) 2 / 2 = 1

위의 경우에는 둘다 1번의 과정으로 끝나기 때문에 비교를 해줄 필요가 없지만 로직상 우리는 저 횟수를 dp배열에 담아둔다.

dp[2] = Math.min(dp[1] + 1, dp[2 / 2] + 1);

dp[i / 2] + 1은 예를들어 현재의 위치가 dp[10]의 값을 구해야할때 해당 값은 dp[5] + 1의 숫자일 수 있다는 것을 의미한다. 5 * 2 = 10 는 1번의 과정이 추가된 것이므로 + 1.

 

이렇게 차례대로 dp[2] ~ dp[n]까지의 숫자를 모두 구한다.

최종적으로 1부터 우리가 구해야하는 n이 만들어 지는 최소값은 dp[n]에 담겨있게 된다.

 

- 새벽 코딩-