[백준 1463번]다이나믹 프로그래밍 1로 만들기

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

1463번: 1로 만들기

#include <iostream>
using namespace std;

int DP[1000001] = { 0 };

int Solve(int v)
{
	int t = DP[v - 1];

	if (v % 3 == 0)
	{
		if (DP[v / 3] < t)
			t = DP[v / 3];
	}
	if (v % 2 == 0)
	{
		if (DP[v / 2] < t)
			t = DP[v / 2];
	}

	return t + 1;
}

int main()
{
	DP[2] = 1;
	DP[3] = 1;

	for (int i = 4; i < sizeof(DP)/4; i++)
	{
		DP[i] = Solve(i);
	}

	int input = 0;
	cin >> input;
	cout << DP[input] << endl;
}

 

이 문제를 정직하게 접근하여 완전 탐색으로 모든 경우의 수를 다 비교한다면 정말 오래 걸린다. 입력값이 10의 6승이라고 나와있는데 입력값이 100 정도만 돼도 연산량이 어마어마 해진다.

 

그래서 미리 DP배열을 만들고 4부터(2,3 은 이미 1인걸 알기에 배열에 미리 고정) 1000000까지 올라가며 DP배열에 값을 할당한다.

예를 들어 Solve 함수에 입력값이 10 이다.

1. -1 을 한다 (9)
2. 2로 나누어 떨어진다면 2로 나눈다. (5)
3. 3으로 나누어 떨어진다면 3으로 나는다. (없음)

그 후 1,2,3으로 나온 값의 배열 인덱스의 숫자가 가장 낮은 값에 +1을 해당 인덱스(10)에 입력한다.

1번 의 값은 9

2번 의 값은 5

9 → 3 → 1 (2번)

5 →4 → 2→ 1 (3번)

그러면 DP [10]의 값은 2+1 =3 이 된다.

그 후 11 , 12 ,13 .... 쭉 이런 식으로 계산하여 배열에 입력하고

사용자의 입력값을 받은 다음 해당 인덱스의 DP 배열 값을 바로 출력해주면 된다.

시간 복잡도는 DP배열 입력 O(n) + 입력값 출력 O(1)

= O(n)