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

Dynamic Programming(DP)로 풀어야 하는 문제

DP란 큰 문제를 작은 문제로 쪼개어 큰 문제를 풀어내는 방법

포인트는 메모리를 이용해 한번 푼 문제는 다시 풀지 않는 것

 

이 문제는 Bottom Up방식으로 풀었다.

예를 들어 18을 1로 만드는 최소 연산을 구하기 위해

2부터 18까지 1을 만드는데 필요한 최소 연산의 갯수를 구한다(0,1은 제외)

 

for문에서 n=18일 때 로직을 나열 해 보면

// 18-1 = 17 => 18에서 -1 연산 한번이면 17이 된다. 17에서 1로 가는 최소 연산 개수는 dp[17]에 저장되어있다.

dp[18] = dp[17] +1 

// 2로 나눠 떨어진다면, dp[17] +1 값과 dp[9] +1 값을 비교해서 최솟값을 저장한다.

if(18%2 == 0) dp[18] = min(dp[18], dp[18/2]+1;

// 3으로 나눠 떨어진다면 dp[9] +1 값과 dp[6]+1 값을 비교해서 최솟값을 저장한다.

if(18%3 == 0) dp[18] = min(dp[9]+1, dp[18/3]+1);

 

결론적으로는

min(dp[17], dp[9], dp[6]) 이 답이 된다.

import java.util.*;

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] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
//            1을 빼는것을 기본값으로 세팅
            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 자체가 아직 익숙하지 않아

풀이 찾아가며 케이스 하나하나 쓰면서 풀어봐도 어렵다.

 

그래도 블로그에 풀이를 써보니 조금은 이해에 도움이 되는 거 같다.