[백준]1463번 1로 만들기(java)

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

1463번: 1로 만들기

백준 1463번 1로 만들기 문제 링크입니다.

핵심

단순하게 3으로 나누고, 2로 나누고, 1을 빼는 순서로 풀게 된다면, 함정에 걸린 것이다. 바로 10이 그 예시이다. 

제일 적게 조합해서 만드는 방법을 0부터 차례대로 생각해야 한다.

정답 코드

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


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

        int x = Integer.parseInt(br.readLine());

        int dp[] = new int[x + 1];

        dp[0] = dp[1] = 0;

        for (int i = 2; i <= x; 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[x]);
    }
}

 

해설

원하는 값 X를 받아들인다.

dp [0], dp [1]은 0으로 설정한다. 연산자를 사용하지 않았기 때문이다.

for문을 봐야 하는데, i를 그 그 자체 값으로 본다.

3으로 나누거나 2로 나누거나 1을 빼는 것은 2 이상부터는 반드시 실행된다.

빼기 1은 언제든지 가능하므로 먼저 1을 뺀다.(for문에서는 반대로 +1 => count 됨)

이후 2로 나누어지거나, 3으로 나누어질 때,

나눈 값의 카운트에 1을 더하는 것과 단순히 그전 dp에 1을 더한 값을 비교한다.

 

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.