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

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

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

1463번: 1로 만들기

동적 계획법(DP)문제이다. 이제 이런 거에 연연하면 안 될 것 같은 게.... DP 문제임을 알게 되니까 당연히 케이스를 나눠서 해야지! 재귀를 부르고 Top-Down 형태로 할거야! 이런 식으로 생각이 들게 된다.

 

그런데 이 문제는 이런 방식으로 풀었더니 안됐다... 그러고 보니 -1이 자꾸 거슬렸다. -1 때문에 결국에는 1부터 N까지 모든 수의 최소 연산 수를 계산하기 때문이다. 그러다 보니 초과가 뜬것이라 생각하고 Bottom-Up 형태로 1부터 순서대로 N까지 구하도록 작성했고, 통과했다.

 

문제를 푸는 논리 자체가 주어졌고 간단한 형태이다. 3으로 나눠 떨어지면 3으로 나눈 값의 최소 연산 수를 생각해야 하고, 2로 나눠 떨어지면 마찬가지 2로 나눈 값의 최소 연산 수도 생각해야 한다. -1은 항상 최소 연산 수를 계산하고~

 

---

20200408

문제를 새로 풀었는데 아예 이전 코드를 지우고 새로운 코드를 붙였다.

재귀로 푸니 제대로 안되길래 반복문으로 bottom-up 형태로 문제를 풀었다.

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

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    if i % 3 == 0 and dp[i//3] + 1 < dp[i]:
        dp[i] = dp[i//3] + 1
    if i % 2 == 0 and dp[i//2] + 1 < dp[i]:
        dp[i] = dp[i//2] + 1

print(dp[-1])

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다