[백준 1463번] 1로 만들기

dp배열을 미리 생성한 뒤 값을 찾는다.

dp인줄 모르고 풀어야하는데.. 궁금해서 알고리즘 분류 봤더니 dp로 바로 풀게됐다.. 

 

어느때 dp로 풀어야할까 ? 

N 값을 보면 N이전의 값을 참조해야하는데, 이렇게 반복적으로 참조되는경우 dp로 풀면 시간단축할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;
int dp[1000001]; //크기 유의, 10^6 인걸 10만으로 잡았다가 계속 런타임에러 ㅠ
int main(void)
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    dp[0] = 0;
    dp[1] = 0;
    for(int i = 2; i<=N+1 ; i++)
    {
    	//3, 2 모두 나누어 떨어지는경우
        if( i%3 == 0 && i%2 == 0) 
        {
        	//3으로 나눴을때 dp값, 2로 나눴을때 dp값, i-1일때 dp값 중 minimum
            dp[i] = min(dp[i/3]+1, min(dp[i/2]+1, dp[i-1]+1));
        }
        // 3으로만 나누어 떨어지는경우
        else if( i%3 ==0 && i%2 != 0) 
        {
        	//3으로 나눴을때 dp값,i-1일때 dp값 중 minimum
            dp[i] = min(dp[i/3]+1, dp[i-1]+1);
        }
        //2로만 나누어떨어지는 경우
        else if( i%3 != 0 && i%2 ==0)
        {
        	//2로 나눴을때 dp값,i-1일때 dp값 중 minimum
            dp[i] = min(dp[i/2]+1, dp[i-1]+1);
        }
        //아예 안나눠떨어지는경우.
        else {
            dp[i] = dp[i-1]+1;
        }
    }
    cout << dp[N] << endl;
}