백준[1463] - 1로 만들기 (Java)

백준에서 DP의 기초 문제인 1463번을 풀어보았다.

1463번: 1로 만들기

 

 

 

문제

 

 

풀이

해당 문제를 보고 어떻게 DP로 풀어야겠다! 는 생각이 바로 들진 않았고, 처음에 그냥 무작정 반복문과 if-else의 조합으로  풀었다. 실패했다.

 

if-else가 아닌 이유

if-else가 아닌 모든 경우의 연산을 시도하고 가장 작은 연산 횟수를 택해야 하기 때문에 모두 if로 행하고 Math.min으로 비교했을 때 가장 작은 값을 택한다.

 

동적 계획법으로 풀 수 있는 이유

여러 해설을 봤는데 가장 이해가 잘 되는 글은 아래 블로그였다.

백준 알고리즘 1463번 문제풀이

 

 

DP의 사용 조건은 아래와 같다.

• 최적 부분 구조(Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 중복 부분 문제(Overlapping Subproblems) : 동일하게 반복되는 작은 문제로 해결해야 한다.

 

해당 문제는 N을 구할 때 {(N-1) 또는 (N/2) 또는 (N/3) 연산 횟수} + 1와 같이 반복되는 작은 문제로 나눌 수 있고, 작은 문제의 답이 큰 문제의 답이 될 수 있으므로 DP를 사용할 수 있는 조건을 충족한다.

 

해결 코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        //bottom-up
        
        int[] dp = new int[n + 1]; //연산 횟수를 저장할 테이블
        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]);
    }
}

 

i는 연산의 대상이며, i가 2부터 시작하는 이유는 1은 이미 1이므로 연산의 최소 횟수가 0이기 때문이다.

 

i를 우선 1로 빼고 연산 횟수를 더해준다(+1). 그다음 2로 나누어 떨어지면 1로 뺀 연산과 비교하여 더 적은 연산 횟수를 dp 배열에 넣는다. 그다음 3으로 나누어 떨어지면 위에서 이미 dp 배열에 넣은 연산 횟수와 비교하여 더 적은 연산 횟수를 dp 배열에 넣는다. 최종적으로 가장 적은 연산 횟수인 값이 dp에 남는다. 이렇게 연산 대상의 값까지 반복한다.

(잊지 말고 각 연산 마다 연산 횟수를 의미하는 +1을 해주자!)