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

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

1463번: 1로 만들기

 

 이 문제는 Dynamic Programming, DP로 해결할 수 있습니다. 

 

 DP를 사용하지 않으면 중복 계산이 계속 발생하기 때문에 DP를 이용한 메모이제이션이 필요합니다. 

 

 DP의 원리인 메모이제이션은 처음 실행되는 연산은 기록해두고 이미 진행된 연산이라면 그 값을 가져오는 방식입니다. 

 

 

연산 과정	연산 횟수 (화살표 개수)
2->1	1
3->1	1
4->2->1  또는  4->3->1	2
5->4->2->1  또는  5->4->3->1	3
6->3->1  또는  6->2->1	2
7->6->3->1  또는  7->6->2->1	3
8->4->2->1  또는  8->4->3->1	3
9->3->1	2
10->9->3->1	3

 

 위 표에서 보시는 바와 같이 중복 계산되는 연산이 생기게 됩니다.  

 

int dp[1000001] = {0, };

 중복 계산을 막기 위해 배열을 하나 선언합니다. 이때 배열의 index는 숫자 N을 나타내고 index에 대응하는 값은 숫자 N을 1로 만들기 위한 최소 연산 횟수를 나타냅니다. 

 

 이 문제는 Top_down, Bottom_up 두 가지 방법으로 해결할 수 있습니다. 

 

 

 

1. Top_down Approach

 

#include<iostream>
#include<cstdlib>
#include<algorithm>

using namespace std;

int dp[1000001] = { 0, };

int topdown(int n) {

	if (n == 1)
		return 0;

	if (dp[n] != 0)  //이미 진행된 연산이라면 return
		return dp[n];

	int& ret = dp[n];
	ret = topdown(n-1) + 1;

	if (n % 2 == 0) {
		dp[n] = min(topdown(n / 2) + 1, ret);
	}

	if (n % 3 == 0) {
		dp[n] = min(topdown(n / 3) + 1, ret);
	}

	return dp[n];
}

int main(void) {

	dp[2] = 1;
	dp[3] = 1;

	int N;

	cin >> N;

	cout << topdown(N);

	return 0;
}

 

 

 

2. Bottom_up Approach

 

#include<iostream>
#include<cstdlib>
#include<algorithm>

using namespace std;

int dp[1000001] = { 0, };

int main(void) {

	dp[2] = 1;
	dp[3] = 1;

	int N;

	cin >> N;

	//bottom_up
	for (int i = 4; i <= N; i++) {
		if ((i % 2 != 0) && (i % 3 != 0))
			dp[i] = dp[i - 1] + 1;
		else if ((i % 2 == 0) && (i % 3 == 0))
			dp[i] = min(dp[i / 3], dp[i / 2]) + 1;
		else if ((i % 2 == 0) && (i % 3 != 0))
			dp[i] = min(dp[i / 2], dp[i - 1]) + 1;
		else if ((i % 2 != 0) && (i % 3 == 0))
			dp[i] = min(dp[i / 3], dp[i - 1]) + 1;
	}

	cout << dp[N];

	return 0;
}