1로 만들기 (백준 1463, 파이썬)

처음엔 예제입력의 2와 10을 기준으로 먼저 생각해 보았다.

 

'1을 뺀다'로 연산 횟수를 한 번 사용하더라도 '2로 나눈다'에서 '3으로 나눈다'로 바뀔 수 있으면 이득이라고 생각했다.

 

그래서 10의 경우에 10은 2의 배수이지만 1을 뺐을 때 9(3의 배수)가 되기 때문에 10에서 바로 2로 나누는 트리인

 

10 -> 5 -> 4 -> 2 -> 1 보다

 

10 -> 9 -> 3 -> 1 이 더 효율적인 방법이 되는 것이었다.

 

10 -> 5 -> 4 -> 2 -> 1 이 방법에서 중간에 등장하는 4의 경우만 해도 아주 작은 숫자일지라도 1을 빼면 3이 되기 때문에

 

4 -> 3 -> 1 로

 

4 -> 2 -> 1 과 비교해서 연산 횟수가 추가되진 않기 때문에 4보다 큰 수들은 당연히 이 방식대로면 3의 배수로 만들기만 하면 횟수에서 이득을 볼 수 있을것이었다.

 

그렇게 생각해서 짠 실패 코드이다.

 

<실패 코드>

n = int(input())
time = 0
 
while n != 1:
    if n%3 == 0:
        n = n//3
        time = time+1
    elif n%2 == 0:
        if (n-1)%3 == 0:
            n = n-1
            time = time+1
        else:
            n = n//2
            time = time+1
    else:
        n= n-1
        time = time+1
 
print(time)

 

수 많은 입력값 중에 내가 생각하지 못한 예외가 있을거란 생각이 들어

 

내가 따로 생각하지 않아도 되게끔, 컴퓨터에서 모든 경우의 수를 직접 다 해보고 가장 먼저 1에 도착한 녀석의

 

결과만 알려주는 코드를 작성했다.

 

<성공 코드>

from copy import copy as copy
 
n = int(input())
results = set()
results.add(n)
time = 0
 
def cal_all(n):
    results.add(n-1)
 
    if (n%3 ==0):
        results.add(n//3)
    elif (n%2 == 0):
        results.add(n//2)
 
while(min(results) != 1):
    temps = copy(results)
    results = set()
    time += 1
    for i in temps:
        cal_all(i)
 
print(time)