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

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

1463번: 1로 만들기

 

 

---

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, dp[1000001] = { 0, 0, };

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

	cout << dp[n];
	return 0;
}

 

 

 

---

 

 

생각할 시간이 없어도 될만큼 쉬웠다. 연산은 -1, /2, /3 세 가지가 가능하다. 이를 반복문을 사용한 동적 계획법으로 풀기 위해 다음과 같은 과정을 거쳤다. 숫자 i에서의 최소 연산 횟수는 dp[i]라고 놓았다.

1. 숫자 i에서의 연산을 1을 빼는 것이라고 가정한다. 따라서 dp[i] = dp[i-1] + 1이다.
2. 숫자 i를 3으로 나눈 연산에 의한 최소 연산 횟수를 구한 후 dp[i]와 비교하여 더 작은 값을 취한다. 즉, dp[i] = min( dp[i/3] + 1, dp[i]) 이다.
3. 숫자 i를 2으로 나눈 연산에 의한 최소 연산 횟수를 구한 후 dp[i]와 비교하여 더 작은 값을 취한다. 즉, dp[i] = min( dp[i/2] + 1, dp[i]) 이다.

끝..!