[백준] 1로 만들기 1463번 (🥈실버3)

사이트

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

1463번: 1로 만들기

문제

 

분석

x가 3으로 나누어 떨어지면 3으로 나누고

x가 2로 나누어 떨어지면 2로 나누고 

2개가 해당이 안될시에 1을 빼면 된다. 

 

쉬울꺼 같지만 의외로 복잡하다. 

 

애매한게 주어진 숫자가 10일때를 생각해보자 

10 9 3 1 

10 5 4 2 1 

 

위 경우의 수를 볼때 먼저 1을 빼면 경우의수가 4가 나오지만 2로 나눌때는 5가지가 된다.. 

또한 6같은 경우는 2하고 3 동시에 나눌 수 있기 때문에 뭔가 애매하다.

 

그래서 거꾸로 생각했다! 처음 숫자를 토대로 나누지말고 맨 아래로 들어가서 경우의 수를 구하는 것이다!! 

for (int i = 2; i < n + 1; i++) {
    dp[i] = dp[i - 1] + 1;
    if (i % 2 == 0) {
        dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
    }
    if (i % 3 == 0) {
        dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
    }
}

핵심 코드이다.

dp[1]은 0으로 초기화 했다. 당연히 1이면 경우의수가 0이니깐! 

그럼 dp[2]는 코드대로 1이 된다. 

 

그럼 첫번째 if문에 걸려 Math.min(1,1) 이렇게 되므로 dp[2]는 1을 최종적으로 가지게 된다.

즉 if문들이 의미하는 것은 

처음 dp[i]=dp[i-1] +1은 결국 1을 빼는 경우의 수를 더한 것이고 

if문들은 1을 뺀 경우의 수보다 작은 큰지 계산하는 것이다. 

 

당연히 if문들이 더 작으면 dp[i]는 그 경우의 수를 가지게 되어 차례 차례 즉 작은 숫자들로부터 채워지면서

최적의 경우의 수를 구하는 것이다. 

 

 

 

전체코드

package dp;

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

public class DP1463 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        dp[0] = dp[1] = 0; // 그냥 초기화 헷갈리니깐..

        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
            }
        }

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

    }
}

결과

 

 

느낀점

살짝 복잡했던 문제였다... 블로그를 참고하면서 내걸로 겨우 만들었다.

DP가 가장어렵다... 열심히 해야지