[백준] 1로 만들기

#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;


int main(){

	int n, tmp;
	cin>>n;
	
	vector<int> count(n+1,1000000);
	
	int index = n;
	count[n] = 0;
	while(index>1){
		tmp = count[index]+1;
		if(index%3==0){
			if(count[index/3]>tmp){
				count[index/3] = tmp;
			}
		}
		if(index%2==0){
			if(count[index/2]>tmp){
				count[index/2] = tmp;
			}
		}
		if(count[index-1]>tmp){
			count[index-1] = tmp;
		}
		index--;
		tmp++;
	}
	cout<<count[1];

}

count 배열에 해당 수까지 연산 횟수의 최솟값을 저장한다.
주어진 n부터 1까지 count배열을 탐색하면서 값을 업데이트한다.
다이나믹 프로그래밍은 결국에 다 해보되, 같은 연산을 반복하지 않도록 하는 것 같다.
다이나믹 프로그래밍에 해당하는 문제인 걸 알고 있었는데도 방법을 생각하는데 시간이 좀 걸렸다.