[백준]JAVA - 1463번: 1로 만들기

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

1463번: 1로 만들기

풀이

이번 문제는 다이나믹 프로그래밍(dp) 문제이다. 다이나믹 프로그래밍에는 Bottom-up 방식과 Top-down 방식이 있는데 이 문제에서는 둘 다 사용이 가능하다. 필자는 Bottom-up 방식이 먼저 떠올라서 반복문으로 풀었다.

 

우선 이 문제에는 "큰 수로 나누는 게 무조건 좋다"의 함정이 있다. 예제 2번을 보면 쉽게 이해할 수 있다.

 

큰 수(2)로 먼저 나누는 방법은 10 → 5 → 4 → 2 → 1로 4번의 연산을 거치지만, 1을 먼저 빼고 3으로 나누게 되면 10 → 9 → 3 → 1로 3번의 연산을 거친다.

 

Bottom-up (반복문) 을 이용한 예제를 보고 대략적인 풀이를 살펴보겠다.

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

이 문제는 연산 횟수를 찾는 문제이므로 0과 1은 연산 횟수가 무조건 0이다. 그렇기 때문에 0으로 선언해주고 dp[2]부터 적용해주면 된다. 이후에 최소 연산 횟수를 구하는 조건으로 문제에서 제시한 3가지만 신경 쓰면 된다.

 

1. 3으로 나누어 떨어지면 3으로 나눈다.

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

2. 2로 나누어 떨어지면 2로 나눈다.

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

3. 1을 뺀다. 

dp[i] = dp[i-1] + 1;

dp[i]는 이전의 연산 횟수 + 1이다. 그렇기 때문에 dp[i] = dp[i-1] + 1이 된다. 1, 2번 예시에서 dp[i-1]+1 대신 dp[i]가 들어간 이유도 이 때문이다.

 

<최종코드>

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int num = Integer.parseInt(br.readLine());
        int[] dp = new int[num+1];
		
        dp[0] = dp[1] = 0;
        for (int i=2; i<num+1; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
        }
		
        System.out.println(dp[num]);
    }
}