(1463) 1로 만들기

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

단계별로 풀어보기

21단계(동적 계획법 1) 8번째

 

 

 

k에 대한 연산 최솟값을 dp[k]라고 하면 dp[k]는 dp[k-1], dp[k/3], dp[k/2] 중 최솟값에 1을 더한 값이다. (두번째, 세번째는 k가 3, 2로 나뉜다면)

다만 이렇게 탑-다운으로 풀면 재귀를 써야하므로 다운-탑으로 구현했다.

자명한 값인 dp[1]= 0을 제외한 값을 INF(문제의 답 범위를 상회하는 값)로 채운 뒤, 값이 구해진 dp[k]에 대해 dp[k+1], dp[3*k], dp[2*k]보다 dp[k]+1이 더 작다면 값을 갱신한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  int n;
  
  cin >> n;
  
  vector<int> dp(n+1, 100001);
  
  dp[1]= 0;
  
  for(int i=1;i<n;i++){
    dp[i+1]= min(dp[i+1], dp[i]+1);
    if(3*i<=n)  dp[3*i]= min(dp[3*i], dp[i]+1);
    if(2*i<=n)  dp[2*i]= min(dp[2*i], dp[i]+1);
  }
  
  cout << dp[n];
  
  return 0;
}