[백준 알고리즘] 1463. 1로 만들기

1로 만들기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	40672	13142	8682	32.585%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

 
xxxxxxxxxx
2

예제 출력 1 복사

 
xxxxxxxxxx
1

예제 입력 2 복사

 
xxxxxxxxxx
10

예제 출력 2 복사

 
xxxxxxxxxx
3

힌트

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

출처

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: dynamiseus
• 문제의 오타를 찾은 사람: jugol

 

 

---

 

풀이

 

처음에는 단순하게 생각해서 3으로 나누어 떨어지면 3으로 나누고, 3으로 나누어 떨어지지 않고 2로 나누어 떨어지면 2로 나누고, 3과 2 둘다 나누어 떨어지지 않으면 1을 빼주는 식으로 알고리즘을 짜주었더니 예제의 2 → 1 은 만족하지만 10 → 3은 만족하지않고 4가 나오는 경우가 발생했다.

뭐가 잘못인지 몰라 이숫자 저숫자 입력해보고 계속 출력해보았지만 10을 입력했을때는 여전히 4가 나왔다.

 

 
xxxxxxxxxx
import java.util.Scanner;
​
public class bj1463 {
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        System.out.print("X = ");
        int x = sc.nextInt();
        
        int cnt = 0;
        
        while (x > 1) {
            
            if (x % 3 == 0)
                x /= 3;
            else if (x % 2 == 0)
                x /= 2;
            else
                x -= 1;
            
            cnt++;
        }
        
        System.out.println(cnt);
        
    }
​
}

 

내가 짠 알고리즘을 수행하면

10/2→5-1→4/2→2/2→1

이렇게 총 4번의 계산이 수행되는데,

 

연산횟수의 최솟값을 충족하는 계산 순서로는

10-1→9/3→3/3→1

이렇게 3번의 계산이 수행되어야 했다.

 

if문의 순서를 바꾸어 보아도 10의 경우에서만 충족하고, 다른 숫자에서는 똑같은 문제가 발생했다.

 

이 문제를 해결하려면,

우선 배열을 만들어 계산횟수를 1씩 증가시키다가 1을 빼주는 것, 2로 나누는 것, 3으로 나누는 것 중 어느 계산이 빠른지 확인하면서 계산횟수 배열에 최솟값을 계속 넣어주면 된다.

 

 
xxxxxxxxxx
import java.util.Scanner;
​
public class bj1463 {
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        System.out.print("X = ");
        int x = sc.nextInt();
        
        int[] cnt = new int[x + 1];
        
        // x가 1이거나 0일 경우 연산의 수는 0번이므로 2부터 시작해도 상관없다
        for (int i = 2; i <= x; i++) {
            cnt[i] = cnt[i-1] + 1;
​
            if(i % 2 == 0 && cnt[i] > cnt[i / 2] + 1)
                cnt[i] = cnt[i / 2] + 1;
​
            if(i % 3 == 0 && cnt[i] > cnt[i/3] + 1)
                cnt[i] = cnt[i / 3] + 1;
​
        }
        
        sc.close();
        
        System.out.println(cnt[x]);
        
    }
​
}
​