C++ 알고리즘 - 백준 1463 1로 만들기 (다이나믹 프로그래밍)

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

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int num[1000002];

int main(void) {
	/************** C++ Init **************/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	/************** C++ Init **************/


	int input;
	int cnt = 0;

	num[1] = 0;
	num[2] = 1;
	num[3] = 1;

	cin >> input;

	for (int i = 4; i < 1000002; i++) {
		num[i] = num[i - 1] + 1;

		if (i % 2 == 0) {
			if (num[i] > num[i / 2] + 1) num[i] = num[i / 2] + 1;
		}

		if (i % 3 == 0) {
			if (num[i] > num[i / 3] + 1) num[i] = num[i / 3] + 1;
		}
	}

	cout << num[input];
}

 

다이나믹 프로그래밍(DP) 의 Bottom-Up 방식인 기본값을 미리 지정 후 알고리즘 구현

작은 문제로 큰 문제를 해결하는 방법으로 동적계획법, 점화식 등으로 불린다.

 

- 기본값

a[1] = 0

a[2] = 1

a[3] = 1

 

- 알고리즘

a[4] = 2

a[5] = 3

a[6] = a[3] + 1 = 2

a[7] = 3

a[8] = a[4] + 1 = 3

a[9] = a[3] + 1 = 2

...

 

숫자가 주어질 때 그 숫자의 -1, /2, /3 을 찾아서 최소 횟수를 저장