[1463] 1로 만들기

이전 문제들은 최대,최솟값을 구하는 문제였는데 연산횟수를 구하라해서 당황했다.

#include <cstdio>
#include <algorithm>
using namespace std;
​
int main(){
    int N = 0;
    int dp[1000000]={0,0,1,1,};
    scanf("%d",&N);
​
    for(int i = 4;i<=N;i++){
       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;
       }
    }
    printf("%d\n",dp[N]);
}

이 문제는 배열을 1부터 사용한다. 각각 1을 1로 만들때 연산은 0, 2를 1로 만들때 연산은 1, 3을 1로 만들때 연산은 1이므로 배열을 0,1,1,로 초기화하고 나머지는 규칙에따라 연산하는 최솟값을 입력한다.