1463 1로 만들기 (동적 계획법) [Silver III]

1463번: 1로 만들기 (acmicpc.net)

동적 계획법

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때 N을 1로 만들기 위해 사용하는 연산의 최소 횟수를 출력하시옹.

 

---

 

동적 계획법 문제입니다. 정수 N만 가지고 계산하는 것이 아니라 0 ~ N까지 최적의 루트를 배열에 저장해가며

큰 문제를 작은 문제로 나누어 푸는 문제입니다.

 

10개의 배열 예시 입니다.

{0, 1, 1, 2, 3, 2, 3, 3, 2, 3}

1 = 0 번의 연산

2 = 1 번의 연산

3 = 1 번의 연산입니다.

 

 

4부터 계산하는 방법은

현재 인덱스에 1, 2, 3번 연산을 통해 이전 인덱스를 불러옵니다.

N = 4일 경우
1. 3으로 나누기 X 안됨

2. 2로 나누기 = 2

3. 1 빼기 = 3

 

2, 3 인덱스를 구했습니다.

배열에서 2, 3번 인덱스의 깊이를 구한 후에 더 작은 값을 추출합니다.

그 값에 + 1을 하여 배열에 넣어줍니다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

static int N;
static vector<int> D;

void result(int id)
{
	int nextDepth = D[id - 1] + 1;
	if (id % 3 == 0)
		nextDepth = min(D[id / 3] + 1, nextDepth); 
	if (id % 2 == 0)
		nextDepth = min(D[id / 2] + 1, nextDepth);
	D[id] = nextDepth;
}  
 
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N; 
	D.resize(N + 1);

	D[1] = 0;
	D[2] = 1; 
	D[3] = 1;
	 
	for (int i = 4; i <= N; i++)
		 result(i); 

	cout << D[N];
}