[백준] 1463 1로 만들기 DP

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

1463번: 1로 만들기

 

분석 :

재귀와 메모제이션을 이용해 풀었다.  

처음에  if (d[n] > 0) return d[n]; 부분을 넣어주지 않아 시간 초과가 났었고 d[1]일때 

n == 1일때 처리를 return 0으로 처리 해주지 않아 100퍼에서 에러로 헤맸다

 

 

c++ 코드 :

//
//  1463_makeOne.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/08/23.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
int d[1000001] = {0, };

int dp(int n){
    int max = 1000001;
    d[1] = d[2] = d[3] = 1;
    if(n == 1) { return 0;}
    
    if (d[n] > 0) return d[n];
    
    if(n % 3 == 0)  { max = min(dp(n/3) + 1, max); }
    if(n % 2 == 0) { max = min(dp(n/2) + 1, max); }
    max = min(dp(n-1) + 1, max); // dp(n-1);
    d[n] = max;
    
    return d[n];
}

int main(){
    int n;
    cin >> n;
    cout << dp(n) << '\n';
    return 0;
}