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

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

 언뜻 보면 단순한 문제로 보인다.

그냥 1, 2, 3번을 구현해서 적용하면 되는 것처럼 보인다. 그러나 그렇지 않다.

연산을 사용하는 횟수의 최솟값을 출력하라는 뜻은 연산을 최고의 효율로 진행하라는 뜻. 

1로 만들기위해 쓸데없는 연산을 진행해선 안된다.

경우의 수를 담을 리스트를 만들었다. 그다음 정수 X에 대한 세 가지 연산에 따른 경우의 수를 리스트에 저장했다.

그리고 경우의 수에 따른 값들에 다시 세 가지 연산을 적용하면 경우의 수 아홉 가지가 나올 것이다. 이를 리스트에 저장한다.

그리고 이를 반복하다가 1로 만드는 순간 연산의 최솟값을 출력하면 된다.

X = int(input())
count = 0
result = [X]
def calculation(x):
    lst = []
    for i in x:
        lst.append(i-1)
        if i%3 ==0:
            lst.append(i/3)
        if i%2 ==0:
            lst.append(i/2)
    lst = set(lst)
    lst = list(lst)
    return lst
while True:
    if X == 1:
        break
    temp = result
    result = []
    result = calculation(temp)
    count += 1
    if min(result) == 1:
        break
print(count)