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

www.acmicpc.net/problem/1463

1463번: 1로 만들기

# 문제

 

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

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

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

 

# 입력

 

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

 

# 출력

 

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

 

# 예시 입력

10

# 예시 출력

3

---

비교적 접근하기 쉬운 문제였다. 동적 프로그래밍 문제이며 1부터 주어진 수 x까지 loop를 돌며 각 숫자를 문제에 제시된 조건 연산을 따르며 1로 만드는 경우의 수 중 최소값을 찾는 문제이다. 숫자 n이 1로 될 수 있는 최소 경우의 수를 arr[] 배열에 담는다.

 

예를 들어 1을 1로 만들 수 있는 최소 경우의 수는 0이다. 이미 자체로 1이므로 즉 arr[1] = 0

2는 2로 나누어 떨어지므로 2 / 2 = 1 즉 arr[2] = 1

3도 마찬가지로 3으로 나누어 떨어지므로 3 / 3 = 1, arr[3] = 1

4는 2로 나누어 떨어지므로 4 / 2 = 2, 2 / 2 = 1 그리고 4 - 1 = 3, 3 / 3 = 1 이다. 어쨋든 arr[4] = 2

 

이쯤 했으면 전체 경우의 수를 찾아 나서는 일은 비효율적임이 분명하다. 내가 생각한 가장 최적의 알고리즘은 다음과 같다.

arr[1] -> 1
arr[2] -> 1
arr[3] -> 1

for i=4 -> x then { //x는 주어진 수, 단 1 <= x <= 1,000,000
	temp = 999999

	if i % 3 == 0? then //case 1
		temp = Math.min(temp, arr[i/3] + 1)

	if i % 2 == 0? then //case 2
		temp = Math.min(temp, arr[i/2] + 1)

	temp = Math.min(temp, arr[i-1] + 1) //case 3 (default)

	arr[i] = temp
    
    
}

return arr[i]

숫자 i에 대해 3가지 케이스를 조건 검사한다.

1) 3으로 나누어 떨어지는가?

2) 2로 나누어 떨어지는가?

3) 조건에 관계 없이 실행

 

temp를 왠만해서 도달할 수 없는 큰 수로 지정해놓고, Math.min()으로 점점 더 작은 값을 찾아 나서는 작업이다.

 

# Whole Code </> - Java 11

public class Main {

    static int getMinCnt(int x) {

        int[] arr = new int[x+1];
        int temp;

        arr[1] = 0;
        if(x >= 2) arr[2] = 1;
        if(x >= 3) arr[3] = 1;
        if(x >= 4)
        for(int i=4; i<=x; i++) {
            temp = 999999;

            if(i % 3 == 0){
                temp = Math.min(arr[i/3] + 1, temp);
                System.out.printf("case 1: arr[%d] = %d\n", i, temp);
            }
            if(i % 2 == 0){
                temp = Math.min(arr[i/2] + 1, temp);
                System.out.printf("case 2: arr[%d] = %d\n", i, temp);
            }
            temp = Math.min(arr[i-1] + 1, temp);
            System.out.printf("case 3: arr[%d] = %d\n", i, temp);

            arr[i] = temp;
        }

        return arr[x];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        if(x < 1 || x > 1000000) System.exit(0);

        System.out.printf("%d\n", getMinCnt(x));
    }
}