백준 1463:1로 만들기

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

백준 1463번 1로 만들기 입니다. 제가 dp를 연습하기 시작했는데, 연습문제로 풀기에 좋은 문제같았습니다.

n이 주어지면 그 숫자를 1로 만드는데, -1 , /2, /3 (나누어 떨어진다면) 만큼 이동합니다. 이동할 때 이동횟수 + 1 을 해주는 것이 중요!

밑에는 제 코드입니다.

#include <iostream>
#include <algorithm>//min함수
#include <vector>
using namespace std;
 
vector<int> dp;
 
int make1(int n) {
    if (n == 1) return 0;//도착
    if (dp[n] != -1) return dp[n];//이미 계산했다면 그 값을 리턴
    int result = make1(n - 1) + 1;//-1만큼 이동해요 (이동하면 cnt++해요)
    if (!(n % 3)) result = min(result, make1(n / 3) + 1);//3의 배수라면 n/3으로 이동해요
    if (!(n % 2)) result = min(result, make1(n / 2) + 1);//2의 배수라면 n/2로 이동해요
 
    return dp[n] = result;//결과를 저장하고 리턴해요
}
 
int main(void) {
    int n;
    cin >> n;
    dp.resize(n + 1, -1);
    cout << make1(n) << endl;
 
    return 0;
}