[BOJ/백준] 1463 (1로 만들기) C++

주제

DP

아이디어

• f(n-3)+1 / f(n/2)+1 / f(n-1)+1 중 min 찾기!!
• 함수 한 번 돌때마다 +1 씩 해주는거 잊지말기

소스코드

/*
boj1463.cpp
2021-01-08
1로 만들기
*/

#include <bits/stdc++.h>
using namespace std;
vector<int> dp;

int f(int n) {
    if (n == 1) return 0;
    if (dp[n] != -1) return dp[n];
    
    int result = f(n - 1) + 1;
    if (!(n % 3))
        result = min(result, f(n / 3) + 1);
    if (!(n % 2))
        result = min(result, f(n / 2) + 1);
    dp[n] = result;
    return dp[n];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    dp.resize(n + 1, -1);
    cout << f(n);
}

배운점

vector의 초기화 : vec.resize(크기,값);

vec.resize(n+1,-1); vector n+1 크기만큼 -1로 초기화
DP 문제 풀 때 주로 사용!!

TopDown -> 재귀 / BottomUp -> for문

TopDown시 재귀 함수 형식

int f(int n) {
    if (n == 1) return 0;
    if (dp[n] != -1) return dp[n];
    
    // 블라블라~
    // f(n - 1) 같은거 불러주기~

    return dp[n];
}