baekjoon 1463:1로 만들기

baekjoon 1463 1로 만들기

1463번 1로 만들기

접근

dp 탑 다운 방식으로 접근해서 풀었다.

코드

//1463
#include <iostream>
#include <queue>
#include <array>
using namespace std;
array<int, 1000001> cache;
int dp(int x);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  fill(cache.begin(), cache.end(), -1);
  cout << dp(n);
  
  
  
  return 0;
}
int dp(int x){
  if(x == 1) return 0;
  int& ret = cache[x];
  if(ret != -1) return ret;
  int temp = dp(x-1) + 1;
  if(x % 2 == 0){
    temp = min(temp, dp(x/2) + 1);
  }
  if(x % 3 == 0){
    temp = min(temp, dp(x/3) + 1);
  }
  return ret = temp;
  
}

배운 점

기초적인 dp 문제였다.