1이 될 때 까지 ( 2018 알고리즘 대회 )

1. 문제 설명

어떠한 자연수 N이 주어지면, 이를 아래 조건 중 하나를 선택하여 최종 1이 될 때 까지 반복하려 한다.

 

     - N에서 1을 뺀다.

     - N을 K로 나눈다.

 

이 때, 위 두 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 구현하면 된다.

 

예를 들어 N = 19, K = 3 가정하자.

 

1. N에서 1을 뺀다 => 18

2. N을 K로 나눈다 => 6

3. N을 K로 나눈다 => 2

4. N에서 1을 뺀다 => 1

 

즉, 위 과정을 최소한으로 진행되는 횟수는 4임을 알 수 있다.

 

2. 문제 해결

핵심 아이디어는 나누기 과정을 최대한 많이 수행하면 된다. 나눌수록 획기적으로 값이 작아지기 때문에, 가능하면 나눗셈 과정이 항상 더 숫자를 빠르게 줄이는 방법이 된다.

 

나눗셈을 많이 포함시키며 과정을 진행하는 건 빠르게 동작할 수 있지만, 최적의 해를 보장하는 근거는 무엇일까?

 

예를 들어보자.

 

1번 case ) N = 132, K = 6

 

=> 6으로 나눈다. ( N = 22 ) 

=> 1로 뺀다 ( N = 21 )

=> 1로 뺀다 ( N = 20 )

=> 1로 뺀다 ( N = 19 ) 

=> 1로 뺀다 ( N = 18 )

=> 6으로 나눈다 ( N = 3 )

=> 1로 뺀다 ( N = 2 )

=> 1로 뺀다 ( N = 1 )

 

2번 case ) N = 54, K = 6 

 

=> 6으로 나눈다 ( N = 9 )

=> 1로 뺀다 ( N = 8 )

=> 1로 뺀다 ( N = 7 )

=> 1로 뺀다 ( N = 6 )

=> 6으로 나눈다 ( N = 1 )

 

N이 클수록 K로 나누었을 때 줄어드는 양이 더 많다.

 

K가 2 이상이면, K로 나누는 것이 1을 빼는 것 보다 항상 빠르게 N의 값을 줄이는 걸 보장한다. 그래서 K를 최대한 많이 나눌 수 있도록 하는 것이 최적의 해를 보장한다.

 

이를 코드로 구현하면 다음과 같다. ( 예제를 참고했다. )

다만 이 방법은 N이 큰 수가 되는 경우에서는 시간 초과 오류가 날 수 있다. 그러므로 1을 빼는 과정을 한 번에 처리하도록 다시 구현해본다.

 

3. 느낀 점

문제의 아이디어는 잘 잡았으나, 구현이 문제였다. 스스로 구현하려니 코드가 지저분하거나 생각한 대로 작동하지 않았다. 확실히 예제 코드가 간결하고 알고리즘을 다 내포하고 있어서 더 깔끔했다.

 

절차대로 조건을 잘 파악해서 구현하는 데 집중을 다 써야 할 것 같다.