백준 1463 - 1로 만들기

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

위의 문제에서 입력 값이 10^6를 고려했을 때 O(N^2)의 경우 1초를 넘어가게 된다.

O(N)안에서 풀 수 있는 방법을 생각했을 때 이전의 값을 이용하여 연산의 최소값을 구하는 방식으로 접근해야 한다.


3으로 나누어 떨어질 때 i/3의 값과 i-1의 값 중에 가장 작은 값을 더해주면 되고 2일 때도 같은 방식이다.
만약에 3과 2로 모두 나누어 떨어지지 않는다면 바로 이전 값인 i-1의 값에 1을 더해주는 방식으로 구하면 된다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int main(){
    
    int n;
    cin>>n;
    
    int* dp=(int*)malloc(sizeof(int)*(n+1));
    memset(dp,0,sizeof(dp));
 
    dp[2]=1, dp[3]=1;
    for(int i=4;i<=n;i++){
        if(i%3==0 && i%2==0)
            dp[i]=min(dp[i/3],dp[i/2])+1;
        else if(i%3==0){
            dp[i]=min(dp[i/3],dp[i-1])+1;
        }else if(i%2==0){
            dp[i]=min(dp[i/2],dp[i-1])+1;
        }else
            dp[i]=dp[i-1]+1;
    }
    cout<<dp[n]<<endl;
    free(dp);
    
    return 0;
}