[백준/python] 1463번 1로 만들기

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

문제 설명:

세 가지 연산을 적절히 사용해서 1을 만드는 문제. 최소한의 연산을 원함.

문제 코드:

x=int(input())
dic={1:0,2:1,3:1}
def fib(x):
    if x in list(dic.keys()):
        return dic[x]
    if x%6==0:
        dic[x]=min(fib(x//3),fib(x//2))+1
    elif x%3==0:
        dic[x]=min(fib(x//3),fib(x-1))+1
    elif x%2==0:
        dic[x]=min(fib(x//2),fib(x-1))+1
    else:
        dic[x]=fib(x-1)+1
    return dic[x]
print(fib(x))

메모리도 시간도 신경써야하니 딕셔너리를 이용함.

탑다운 방식처럼 찾고싶은 문제의 답을 찾기위해 작은 문제들로 쪼개다가 1,2,3같이 처음 답을 찾은 순간부터 답을 채워나감. 이때 한 번 찾은 답은 저장해두므로 중복연산 방지

처음 풀이를 생각할 때 위처럼 2와 3으로 모두 나뉠 때== 6으로 나뉠 때, 2로만 3으로만 나뉠 때, 그게 아닐 때==-1해줌 이런 식으로 경우를 모두 나눠 풀었는데 다른 이들의 코드를 보니 이렇게 나누지 않고 어차피 2로 3으로 나누고 안떨어지는 나머지는 -1을 한것과 동일한 연산이란걸 생각하고 만든 좀 더 간결한 코드도 있었음. 남의 코드와 비교하며 내 코드의 효율이나 시간복잡도 등 비교할 수 있었음.