BOJ - 1463. 1로 만들기 (C++)

1463. DP

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

 

[풀이]

BFS로도 풀이 가능하지만 점화식을 세워 DP로 풀이가 가능하다.

d[1] = 0으로 두고 입력값 X일 때 연산의 최솟값을 d[X]라고 하면 d[2]부터 d[X]까지 for문으로 돌아가며 최솟값을 구할 수 있다.

#include "bits/stdc++.h"
using namespace std;

int d[1000001];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int input; cin >> input;
	
	for (int i=2; i<=input; i++){
		vector<int> tmp;
		if (i%3==0) tmp.push_back(d[i/3] + 1);		// 3으로 나눌 때
		if (i%2==0) tmp.push_back(d[i/2] + 1);		// 2로 나눌 때
		tmp.push_back(d[i-1] + 1);			// 1을 뺄 때
		
		d[i] = *min_element(tmp.begin(), tmp.end());	// 셋 중 최솟값을 저장
	}
	cout << d[input];
}