✔ 풀이를 위한 아이디어
- 동적 프로그래밍 (Dynamic Programming)
✔ 수정 전 코드
import sys
def make_one(x, count):
if x == 1:
print(count)
return
if x == 2:
x = x // 2
elif x % 3 == 0:
x = x // 3
elif (x & (x-1)) == 0: #2의 n제곱 판별
x = x // 2
elif x % 3 == 1:
x = x - 1
elif x % 3 == 2 and x % 2 == 0:
x = x // 2
elif x % 3 == 2 and x % 2 == 1:
x = x - 1
count += 1
make_one(x, count)
if __name__=="__main__":
X = int(sys.stdin.readline())
count = 0
make_one(X, count)- 처음에는 그리디 알고리즘(Greedy Algorithm)을 통해 구현할 수 있을 것이라고 생각했다. 그래서 다양한 케이스들을 직접 테스트 해보며 나름 완벽하다고 예상되게 코드를 짜보았다.
- 그러나 1284, 1793과 같은 숫자를 넣었을 때 오류가 발생하였고, 결국 모든 경우를 다 고려해보는 동적 프로그래밍(Dynamic Programming)으로 짜야한다는 것을 인정할 수밖에 없었다.
✔ 수정 후 코드
X = int(input())
dp = [-1, 0, 1, 1]
#점화식: dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1
for i in range(4, X+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)
print(dp[X])- 동적 프로그래밍(Dynamic Programming)을 사용해본 것은 처음이었기 때문에, 구글링의 도움을 조금 얻었다..
- 오히려 코드가 더 간결해지는 것을 보고 (물론 더 많은 케이스들을 고려해보는 코드이지만) 동적 프로그래밍이 나쁘지 않은 선택지라는 것을 깨달았다.
- 이 코드는 동적 프로그래밍 중에서도 작은 문제부터 차근차근 구해가는 Bottom-Up 방식이며, 각 숫자에서 3가지 연산 중 가능한 모든 경우를 비교해서 최솟값을 저장한다.
- 수정 전 코드를 아무리 보완해서 제출해도 틀리길래, 결국 모든 경우를 고려해보는 동적 프로그래밍을 사용하여 맞추었다.
처음으로 풀어본 DP 문제!
✔ 관련 개념
- 동적 프로그래밍 (Dynamic Programming): https://galid1.tistory.com/507
