cpp) 백준 1463: 1로 만들기

Problem

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

1463번: 1로 만들기

 

 

Solution

#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n;
    cin >> n;
    int dp[10000001];

    dp[0]=0;
    dp[1]=0;
    dp[2]=1;
    dp[3]=1;

    for(int i=4;i<=n;i++){
        dp[i]=dp[i-1]+1;
        if(i%2==0) dp[i]=min(dp[i],dp[i/2]+1);
        if(i%3==0) dp[i]=min(dp[i],dp[i/3]+1);
    }

    cout << dp[n] << '\n';
  
    return 0;
}

 

DP는 bottom-up 방식으로 기본적인 값들은 미리 구해놓고 순차적으로 계산하는 풀이 방법이다. 우선, 기본적인 값으로 dp[0], dp[1], dp[2], dp[3]을 구해놓는다.  

 

 

 

Reference

https://velog.io/@matcha_/BOJ-%EB%B0%B1%EC%A4%80-1463-CDP

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