이번 문제는 (BOJ) 백준 1463번 1로 만들기 문제이며

다이나믹 프로그래밍 문제입니다.

문제링크

언제나 다이나믹 프로그래밍은 점화식을 세우는게 어렵습니다. ㅠㅠㅠ

그리고 다이나믹 프로그래밍인지 아닌지를 파악 하는데에도 시간이 걸립니다.

우선적으로 다이나믹 프로그래밍인지 확인 하는 가장 빠른 방법은,

저의 개인적인 생각으로

1) 모든 경우의 수를 따져야 하는가 ? + 그 모든 경우의 수를 따졌을 때 시간 초과가 날 것인가 ?

2) 문제에 주어진 것의 역방향으로 접근 할 수 있는가?

3) 최대값이 크지 않지만, 계수승으로 (n^x) 경우의 수가 늘어나는가

이렇게 생각 하고 시작 합니다.

풀이

저도 처음에는 우선순위를 부여하며 풀어 봤습니다.

-1 해서 3이나 2로 나누어 떨어지게 만들면 최적의 방법이 되지 않을까?

했지만 그렇지 않더라구요.

우선 순위가 그때그때 달라집니다. 결국 우선 순위를 매길 수 없고

우선 순위를 매기더라도 직접 몇단계 시뮬을 돌리도록 설계 해야 하기 때문에

결국 시간만 걸리고 좋은 방법이 아닙니다.

그리하여 이 문제는 문제에 주어진 내용대로 접근 하지 않고

1부터 시작하여 역방향으로 올라갑니다.

각각 dp 로 배열에 그 숫자까지 도달하는 최소의 수를 구하며, 올라갑니다.

그럼 n번째의 가장 작은 접근 방법은 어떻게 찾을까요?

문제에 주어진 조건대로

dp[n-1] + 1 / dp[n/2] +1 / dp[n/3] +1 중 하나가 최적의 접근 방법이 될 겁니다.

이중 가장 적은 값을 대입 해 주면 됩니다.

저같은 경우

void checker(int n , vector<int> &dp) {
	dp[n] = dp[n - 1] + 1;
	if (n % 2 == 0 && dp[n/2]+1 < dp[n])
		dp[n] = dp[n / 2] + 1;
	if (n % 3 == 0 && dp[n / 3] + 1 < dp[n])
		dp[n] = dp[n / 3] + 1;
}

위와 같이 구현 하였습니다.

즉 이런식으로

시간이 3n 으로 줄어들게 됩니다.

만약 역순으로 왔다면 ?^3 으로

몇번이 걸릴지 모르지만, 3제곱으로 시간복잡도가 뛰어 버리기 때문에

이 방식이 훨씬 더 시간을 절약 하게 됩니다.

코드

#include <iostream>
#include <vector>>

using namespace std;

void checker(int n , vector<int> &dp) {
	dp[n] = dp[n - 1] + 1;
	if (n % 2 == 0 && dp[n/2]+1 < dp[n])
		dp[n] = dp[n / 2] + 1;
	if (n % 3 == 0 && dp[n / 3] + 1 < dp[n])
		dp[n] = dp[n / 3] + 1;
}
int main() {

	int n;
	cin >> n;

	vector<int> dp(n+1, 999);

	dp[0] = 0;
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	for (int i = 4; i <= n; i++) {
		checker(i, dp);
	}
	cout << dp[n];
	return 0;
}

후기

dp 문제는 언제나 생각하는데 시간이 오래걸리지만,

막상 점화식을 짜서 대입 하면 코드는 항상 짧게 짜지는 편이에요.

그러니 dp 문제에 맞딱들였다 하면

무작정 코딩을 시작 하는 것 보단

최적화를 먼저 한 후 변수 제어 후

코딩을 시작 해도 충분히 시간 내에 할 수 있습니다. !

그럼 모두 열코딩!