문제

문제 링크

어떻게 접근할 것인가

  • 어떻게 하지.. 하다가 그냥 1부터 1000000까지 다 하나씩 업데이트 시켜주기로 했다.
  • 그리고 나서 선택하니까 정답…

코드

#include <cstdio>
#include <vector>

using namespace std;

#define INF 10000000
int n;
int main(){
    vector<int> arr(3000010, INF);
    scanf("%d", &n);
    arr[1] = 0;
    for(int i = 1; i <= 1000000; i++){
        int v = arr[i] + 1;        
        if(v < arr[i*3])arr[i*3] = v;
        if(v < arr[i*2])arr[i*2] = v;
        if(v < arr[i+1])arr[i+1] = v;
    }
    printf("%d", arr[n]);
}

느낀점

  • 설마 이렇게 푸는게 답이겠어 했던 방법이 답이었다.
  • 때론 일단 되는 방법을 먼저 생각해서 풀어보자.
  • 문제를 똑바로 이해하지 못하면 막히게 되어있다.