[백준] - 1463번: 1로 만들기(Python)

문제📝

풀이💡

• dp에 계산된 값을 저장한다.
• 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되서 1을 빼준다.
• 동적계획법을 이용해서 상황에 따라 나눈다.

코드💻

# 백준 Silver3 - 1463(1로 만들기)
# 문제링크: https://www.acmicpc.net/problem/1463

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

for i in range(2, n+1):
    dp[i] = dp[i-1]+1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1) 
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    ## 1을 더하는 것은 dp는 결과가 아닌 계산한 횟수를 저장하는 것이기 때문이다.
print(dp[n])

결과😎

느낀점👨‍💻

지금까지 풀어본 문제와는 다른 방법으로 풀어야 할 것 같아서 알아보니 동적 계획법을 사용해서 풀어야했다. 동적 계획법을 공부한 적은 있는데 이렇게 문제로 적용해서 풀어본 적은 처음인 것 같다. 이 문제 덕분에 오랜만에 동적 계획법도 다시 공부하였고 아직도 부족한 점이 많다는 것을 인지해준 것 같다.

Sinbmil의 알고리즘 문제 코드

-> https://github.com/Sinbmil/Algorithm-Study