[백준 #1463 c++] 1로 만들기, 동적계획법

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

1463번: 1로 만들기

 

이 문제는 동적계획법을 입문하기에 매우 좋다.

동적계획법(Dynamic Programming, DP)이라는 말은 도대체 뭘 설명하는지 알 수가 없지만 실상은 Memoization이라고 생각한다.

DP에서 최적 부분 구조라는 특성이 있는데, 전체 구간의 계산 결과를 특정 구간들의 계산된 결과의 합으로 나타낼 수 있다는 것이다. Memoization은 이와 비슷한 말이지만 조금 다르다.

 

Memoization은 Top-Down 또는 Bottom-Up 중 어떤 방식으로든지 이미 계산한 구간을 반복하여 계산하지 않도록 하기 위해 필요하다. 만약 순서를 따르지 않고 무작위로 골라서 계산해야 하는 경우에는 Memoization을 할 수 없다는 얘기다.

 

이 문제의 접근을 Bottom-Up Memoization으로 시작한다면 꽤나 빨리 풀 수 있을 것이다.

---

제시된 입력값에서 가장 작은 값인 1부터 보자.

1은 이미 정답이기 때문에 연산이 필요없다. 즉 출력값이 0이다.

2의 경우 2로 나누거나 1을 빼는 방식으로 1회의 연산을 거친다. 즉 출력값이 1이다.

3역시 마찬가지로 해서 출력값이 1이 된다.

 

이렇게 작은 값부터 순차적으로 계산한다고 해보자.

4를 계산한다면 어떻게 될까?

4는 2로 나누거나 1을 빼는 연산이 가능하다.

이 때 2로 나눈 경우에는 2가 되고, 1을 빼는 경우에는 3이 되는데,

2와 3은 이전에서 이미 계산을 끝냈기 때문에 반복할 필요가 없다.

---

즉 이 단순한 원리에서

 

[4의 출력값] = ([2의 출력값] + 1)과 ([3의 출력값] + 1) 중 작은 값

 

이라는 일종의 점화식이 나온다.

 

 

이 점화식을 토대로 코드를 짜면 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1e9;

int memo[1000001];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	cin >> n;

	memo[0] = 0;
	memo[1] = 0;
	for (int i = 2; i <= n; i++) {
		memo[i] = INF;
		if (i % 3 == 0) {
			memo[i] = min(memo[i], memo[i / 3] + 1);
		}
		if (i % 2 == 0) {
			memo[i] = min(memo[i], memo[i / 2] + 1);
		}
		memo[i] = min(memo[i], memo[i - 1] + 1);
	}

	cout << memo[n];
}

*min(x, y) 함수를 사용하기 위해서는 algorithm 또는 utility 헤더파일을 필요로 한다.

 

한 번의 루프에서 memo[i]는 최대 3번의 대입을 거치면서 최소값을 가지게 된다. (사실 코드에서 INF 대입은 불필요하다. 하지만 일반적으로 최소값을 찾는 문제에서는 계산하기 전 무한대 값으로 초기화하는 게 기본이라고 보면 된다.)

그렇게 계산된 memo[i]는 이후에 계산할 필요가 없다.

 

이 문제를 Brute Force로 푼다면 n = 1,000,000 이라고 했을때

주어진 연산의 결과마다 3개의 연산을 적용하게 된다.

이때 연산을 거칠 때 마다 n값이 작아져서 총 횟수는 -1 연산만 했을 때 n번이 되고

그 루트의 개수는 최대 3의 1,000,000제곱이나 된다. (중복순열)

 

하지만 이를 동적계획법으로 푸는 순간 3번의 연산을 n번 수행하기 때문에

O(N)이 된다.