[백준/1463] 1로 만들기 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 # n-1 연산, 횟수 저장 (+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1) # 1을 더하는 이유: dp는 계산 값이 아닌 횟수를 저장
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])

---

✔ 후기

만만하게 봤다가 큰 코 다쳤지요..?

if continue ~ elif continue 했다가 지맘대로 돌아가서 당황했다...

사실 맞는 코드도 아니여서 적지는 않았지만... (대충 적어본거라 요구하는 문제에 맞는 구현도 아니었음)

 

https://jae04099.tistory.com/199

[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)

이 분 블로그 보면서 그리디랑 동적 계획법 차이도 얼떨결에 배웠다!

그리디는 반례가 없어야 하고 동적은 모든 가능성을 두고 그 안에서 해당되는 조건을 골라야하는 것이다.

생각해보면 동적 문제를 풀떄 항상 min 또는 max 함수를 사용했기 때문에 아 그렇구나~ 싶었다.

 

값을 dp에 저장하는 것이 아니라 횟수를 저장해야한다는 방법을 생각못해서 코드를 봐도 이해가 잘 안갔었다.

저녁에 한 번 더 풀어봐야겠다