P.1463 1로 만들기

castlehi·2022년 3월 21일

목록 보기

42/67

1463 1로 만들기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초 (하단 참고)	128 MB	189946	61363	39004	32.014%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

코드

import java.io.*;

public class P_1463 {

    static int n;
    static int[] nbs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        nbs = new int[n + 1];
        find_result();

        bw.write(Integer.toString(nbs[n]));
        bw.flush();
    }

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

코드 설명

들어올 수 있는 최대 수가 $10^6$ 이고 바로 바로 계산을 해야 0.1초만에 연산이 가능하니 dp의 bottom-up 방식을 이용했다.

작은 계산부터 시작해서 최소값을 구할 것이기 때문에 가장 작은 계산인 -1을 빼는 것부터 시작을 했다.
그래야 nbs[i]에 최대값으로 추정되는 값이 들어간 채로 계산을 시작하게 된다.

nbs[i] = nbs[i - 1] + 1 인 이유는 예시를 보면 알 수 있다.

4와 5라는 숫자에 대한 값을 구한다고 가정했을 때,

4는
$4 - 1 = 3$
$3 / 3 = 1$
이 두 연산으로 가능하기 때문에 2라는 값을 가진다.

반면 5는
$5 - 1 = 4$
를 하게 되면 $nbs[4] + 1$ 로 바로 구할 수 있다.

이렇게 값을 세팅해놓고 i가 3으로 나누어지는지 2로 나누어지는지를 확인한다.
3으로 나누어질 경우 현재 nbs[i]에 저장되어있는 값과 새로 구한 값을 비교를 해야하는데 nbs[i / 3] 값이 그 기준이 된다.

3과 6이라는 숫자에 대한 값을 구한다고 가정했을 때,

3은
$3 / 3 = 1$
이 최소값이기 때문에 $nbs[3] = 1$ 이라는 결과를 가진다.

6은 bottom-up 방식부터 시작을 하면
$6 - 1 = 5$
이기 때문에 $nbs[5] + 1$ 로 4라는 값으로 시작하게 된다.
(nbs[5]를 구하는 과정은 생략했다.)

6은 3으로 나누어지기 때문에
nbs[i] = Math.min(nbs[i], nbs[i / 3] + 1) 이 문장을 수행할 수 있다.
$nbs[i / 3]$ 은 $nbs[2]$ 를 의미하는데 $nbs[2]$ 는 1이다.
그런데 6에서 시작한 계산은 3으로 나눈 연산을 1회 포함하기 때문에 $nbs[i / 3] + 1$ 을 해 주어야 한다.
이제 $nbs[2] + 1$ 즉, 2와 현재 저장되어 있는 값 $nbs[6]$ 을 비교하게 되는데 당연히 2가 더 작기 때문에 $nbs[6]$ 은 2가 된다.