DP의 대표적 문제 - BOJ 1463번

#include<iostream>

using namespace std;

int dp[1000001];

int min(int a, int b) {
	if (a > b) return b; return a;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	dp[1] = 0;

	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];
}

동적 프로그래밍(DP)이란?

큰 문제를 작은 문제로 분할하여 문제를 푸는 방법.

​

※ dp[입력] = 연산 사용 횟수

​

풀이 :

1. 정수 x을 입력받는다.

2. 입력이 1일때는 연산을 사용하지 않아도 되므로 결과 값이 0. 즉, dp[1] = 0;

3. 입력이 2일 때부터 정수 n까지 각각의 연산을 사용하였을 때의 출력 값(=연산 사용 횟수)가 가장 작은 값으로 설정한다.

4. 순차적으로 n까지 계산하게 되고, 결국 마지막엔 n를 입력으로 하였을때의 연산 횟수를 출력한다.