[백준] 1463번 1로 만들기

출처

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

1463번: 1로 만들기

문제

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

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

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

입력

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

출력

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

예제

내코드

점화식을 찾아 문제를 해결하는 Dynamic Programming를 사용하면 쉽게 풀 수 있는 문제였습니다. 다만 DP에 대한 이해를 한 후 직접 과정을 써보면서 진행해보시면 좋을 것 같습니다.

문제에서 주어진 10을 예시로 들면 10->5->4->2->1 보다 10->9->3->1 로 가는 것이 1로 만드는 과정이 한번 더 줄어듭니다.

과정을 이해하기 위해서 6까지 한 단계씩 진행해보았습니다.

1. mat[1] = 0 으로 초기값을 설정합니다. 1은 이미 1이기 때문에 0입니다.

이제 반복문을 2부터 입력받은 숫자 10까지 돌게합니다. 반드시 입력받은 숫자까지 돌아야합니다.

mat[i] = mat[i - 1] + 1;

2. mat[2] 는 먼저 mat[2] = mat[2-1] + 1로, 들어온 값-1 의 배열값에서 1이 증가된 값인 1이 넣어집니다.

 if (i % 2 == 0)
                mat[i] = Math.min(mat[i], mat[i / 2] + 1);

이후 mat[2]의 2는 2로 딱 떨어져 나누어지므로 if문 내로 들어가게 됩니다. 여기서 mat[2]의 값과 mat[2/2]+1 의 값을 비교하게 되는데 이는 처음에 [i-1]+1 값보다 mat[i/2]+1의 값이 더 작은지 확인하는 과정입니다.

mat[2] = min(mat[2] , mat[2/2]+1) = min(1, 1) = 1 이 들어갑니다.

위 과정을 반복해 진행합니다.

3. mat[3] = min(mat[3], mat[3/3]+1) = min(2,1) = 1

4. mat[4] = min(mat[4], mat[4/2]+1) = min(2,2) = 2

5. mat[5] = mat[5-1] +1 = 2+1 = 3

6. mat[6] = min(mat[6], mat[6/2]+1) = min(4, 2) = 2 -> mat[6] = min(mat[6], mat[6/3]+1 = min(4, 2) = 2 ->2로 나누었을때의 최솟값을 가지고 3으로 나누었을 때의 최솟값과 비교합니다.

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int mat[] = new int[1000001];
        mat[1] = 0;

        for (int i = 2; i <= N; i++) {
            mat[i] = mat[i - 1] + 1;

            if (i % 2 == 0)
                mat[i] = Math.min(mat[i], mat[i / 2] + 1);

            if (i % 3 == 0)
                mat[i] = Math.min(mat[i], mat[i / 3] + 1);
        }
        System.out.print(mat[N]);
    }
}