[동적계획법, 난이도 중] 백준 1463번 1로 만들기

첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다.

동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다.

해답을 바로 구하는것은 그리디(탐욕) 알고리즘이다.

동적 계획법은 대부분 점화식을 요한다. 

 

그런데 해답을 바로 구하는 것이 아니라는 말이 무슨말인가 이해가 안될 수 있다.

이번 문제가 이를 설명할 좋은 예가 될것이다.

 

예제 입력2 에서

입력값으로 10을 줬을 때 3이 출력되는데 아래 사진이 접근 과정이다.

s배열=save배열

식을 보면 인덱스 0부터 순차적으로 계산해나가며 이전에 계산했던 값을 활용하고 있다. 

다르게 말하면 입력값 10까지의 경우를 모두 계산했다는 말도 된다.

이러한 방식으로 접근하는 알고리즘이 동적계획법이다.

 

이제 본격적으로 위와 같은 식이 어떻게 도출 된것인지 보자.

문제에서는 해당 수를 3으로 나누든 2로 나누든 1을 빼든 여러 방법을 반복하여 1을 만들라고 한다.

이를 역으로 1부터 계산한 것이다.

(3으로 나누어 떨어지는 경우, 2로 나누어 떨어지는 경우, 1을 뺀 경우) 모든 경우의 결과 중 최솟값을 갱신해나가면 된다.

예를 들어 s[6]은 (s[2]+1=2), (s[3]+1=2), (s[5]+1=4) 중 최솟값인 2로 갱신되고,

s[10]은 (s[5]+1=4), (s[9]+1=3) 중 최솟값인 3으로 갱신된 것이다.

 

 

 

#include <iostream>
using namespace std;
int save[1000001];
int min(int x, int y, int z) {
	if (x <= y) {
		if (x <= z) return x;
		else return z;
	}
	else if (y <= z) return y;
	else return z;
}
int main() {
	int a;
	cin >> a;
    save[0] = 0;
	save[1] = 0;
	for (int i = 2; i <= a; i++) {
		int x = 1111111;
		int y = 1111111;
		int z = 1111111;
		if (i % 3 == 0) {
			x = save[i / 3] + 1;
		}
		if (i % 2 == 0) {
			y = save[i / 2] + 1;
		}
		z = save[i - 1] + 1;
		int result = min(x, y, z);
		save[i] = result;
	}
	cout << save[a];
}