[백준] 1463번: 1로 만들기 / C++

풀이 문제 : 백준 1463번 : 1로 만들기
풀이 언어 : C++
알고리즘 : DP
문제링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제 요약

---

 

접근 방식

---

가능한 연산이 세가지 뿐이니까 세가지 연산을 모두 해보고 횟수가 가장 적은 것을 누적하며 구하고자 하는 값까지 찾아올라가는 방식으로, dp 알고리즘을 사용했다.

 

코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000000];

int main() {
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	int n;
	cin >> n;

	for (int i = 4; i <= n; i++) {
		int m = dp[i - 1] + 1;
		if ((i % 2) == 0) m = min(m, dp[i / 2] + 1);
		if ((i % 3) == 0) m = min(m, dp[i / 3] + 1);
		dp[i] = m;
	}
	cout << dp[n];

	return 0;
}