[C++/알고리즘] 백준 1463 (1로 만들기)

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

1463번: 1로 만들기

 

 

 

다이나믹 프로그래밍으로 분류되어 있는 문제이며 재귀의 방식으로 문제를 해결하였다.

 

n에서 1을 뺐을 때 정수 N을 만드는 경우의 수 D[n]은 

D[n] = D[n-1] + 1 이다.

또한 n을 2로 나누었을 때 정수 N을 만드는 경우의 수 D[n]은

D[n/2] = D[n/2] + 1 이고

n을 3으로 나누었을 때 정수 N을 만드는 경우의 수 D[n]은

D[n/3] = D[n/3] + 1 이다. 

 

그러므로

n에서 1을 뺐을 때의 값을 먼저 저장해두고

n이 2로 나누어 떨어지면 2로 나누었을 때의 값을 계산하고

2로 나누었을 때의 값이 이미 저장된 d[n]보다 작을 때

현재 저장된 d[n]의 값을 2로 나누었을 때의 값과 바꾸어 준다.

 

3으로 나누어 떨어지면 위와 같은 방식으로 값을 비교한다. 

 

1을 먼저 빼고 2를 나누고 3을 나누는 순으로 구성한 이유는 N은 3으로 나누었을 때 가장 작은 수가 되기 때문이다. 

그래서 경우의 수가 더 작게 나올 확률이 크다.

 

#include <iostream>

using namespace std;
const int MAX_NUM = 1000000;

int d[MAX_NUM];

int cal(int n)
{

	if (n == 1)return 0;
	if (d[n] > 0) return d[n];

	d[n] = cal(n - 1) + 1;

	if (n % 2 == 0) {
		int temp = cal(n / 2) + 1;
		if (temp < d[n]) {
			d[n] = temp;
		}

	}

	if (n % 3 ==0) {
		int temp = cal(n / 3) + 1;
		if (temp < d[n]) {
			d[n] = temp;
		}
	}
	return d[n];
}
int main()
{
	int n;
	cin >> n;
	cout << cal(n) << endl;
}