백준 알고리즘 - 1로 만들기 (1463) [Python]

 문제

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 문제 상황

 

- 연산 3가지를 이용해서 주어진 정수를 1로 만드는데 필요한 최소한의 연산 횟수를 출력한다.

 

 

 

 해결 전략

 

- 부분 문제의 중복이 발생하므로 동적 계획법을 활용한다. 연산이 3개이므로 각각의 경우를 나누어 연산한다.

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
cache = [0,0,1,1] + [0]*(N-3)
counts = 0    
for i in range(4, N+1):
    if i % 6 == 0 :
        cache[i] = min(cache[i//3], cache[i//2], cache[i-1]) + 1
        continue
    elif i % 3 == 0:
        cache[i] = min(cache[i//3], cache[i-1]) + 1
        continue
    elif i % 2 == 0:
        cache[i] = min(cache[i//2], cache[i-1]) + 1
        continue
    else :
        cache[i] = cache[i-1] + 1
print(cache[N])

 

# 다른 사람의 풀이
n = int(input()) # 숫자 입력
dp = [0,0,1,1] # 0과 1은 0번으로, 2와 3은 1번의 연산으로 1 가능
for i in range(4, n+1):
    dp.append(dp[i-1]+1)
    if i%2 ==0 :
        dp[i] = min(dp[i], dp[(i//2)]+1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[(i//3)]+1)  # 이게 elif면 틀린다.
print(dp[n])

 

 

 해설

 

- 사실 직관적으로 3과 2로 모두 나눌 수 있을 때에는 3으로 나눌 때 피연산자가 작아지는 속도가 훨씬 크기 때문에 무조건 2로 나눌때보다 연산이 유리하지만, 혹시나 하는 마음에 6으로 나눌 수 있을 때에는 모두 검사하는 조건을 주었다.

 

- 다른 사람의 풀이는 조건이 훨씬 간단했다. 1을 빼준 경우는 최소한의 조건이므로 넣어주고, 그 후 2로 나눌 수 있을때, 3으로 나눌 수 있을 때 조건을 넣어 비교해주었다. 

 

- 코드만 보면 아래가 더 깔끔하지만 속도는 위가 더 빨랐다. 아래의 경우 append를 반복해야하는데다가 if문을 무조건 전부 체크해야하므로 오히려 느렸던 것 같다.

 

 

 

 새로 학습한 것 & 실수 

 

- 재귀로 memoization하는 것은 훨씬 까다롭다. 반복문 사용을 피하지 말자