20210620#(43) 백준 1463 1로 만들기(다이나믹 프로그래밍)

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

1463번: 1로 만들기

 

#1 

메모리200680kb  시간168ms

N=int(input())
dp=[0,0,1,1]

for i in range(4,N+1):
  dp.append(dp[i-1]+1)
  if i%2 == 0:
    dp[i]=min(dp[i//2]+1,dp[i])
  if i%3 == 0:
    dp[i]=min(dp[i//3]+1,dp[i])
    
print(dp[N])

 

 

#2

메모리133180kb 시간128ms

N=int(input())
dp=[0 for _ in range(N+1)]

for i in range(2,N+1):
  dp[i]=dp[i-1]+1
  if i%2==0:
    dp[i]=min(dp[i//2]+1,dp[i])
  if i%3==0:
    dp[i]=min(dp[i//3]+1,dp[i])
print(dp[N])

 

 

다이나믹 프로그래밍 Dynamic programing

 

-하나의 문제를 단 한번만 풀게하는 알고리즘

 

다음 두가지 가정하에 이용 가능한 알고리즘이다.

1. 큰 문제를 작은문제로 나눌 수 있을때

2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일할 때

 

다음 영상은 유튜브 동빈나 채널에서 다이나믹 프로그래밍에대해서 쉽게 설명하고있는 영상이다. 짧으니 한번 보는걸 추천한다.

https://www.youtube.com/watch?v=FmXZG7D8nS4

출처:  유튜브 동빈나 21강 - 다이나믹 프로그래밍(Dynamic Programming) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #21 ]