백준 알고리즘 1463

이번 문제는 DP(Dynamic Programing)문제였다. 이전에 DP에 대한 이해를 하고 문제를 푼 적이 없어서 문제를 풀기 전에 간단하게 DP에 대해 알아보았다. 출처는 아래의 Blog이다.

2. Dynamic Programming (DP)

• Dynamic Programming(이하 DP)은 우리말로 동적 프로그래밍(DP)이라고 한다.
• RL에서는 기본적으로 확률 동적 프로그래밍 (Probabilistic Dynamic Programming) 기법을 사용하게 된다.
  • 즉, 기본적인 DP 모델에 확률 이론이 포함된다는 이야기이다.
• 따라서 여기서는 먼저 간단하게 동적 프로그래밍(DP)이 뭔지 확인해보고 넘어가도록 하자.
  • 물론 동적 프로그래밍을 이해하기 위해서는 먼저 결정적 프로그래밍(deterministic programming) 방식을 무엇인지 이해하고 있어야 한다.
    • 여기서는 이런것까지 언급할 시간이 없다. 바로 동적 프로그래밍이 뭔지만 보고 넘어가도록 하자.
    • 물론 학교 다닐때 다 배운 내용이기도 하다. (예를 들어 BFS , DFS 등이 대표적인(가장 쉬운) 결정적 프로그래밍 기법.)
    • 최단거리 같은거 많이 구해보았을 것이다.

동적 프로그래밍의 기초

• 최적화 기법 중 하나로 재귀(recursion)를 이용하여 최적화 솔루션을 얻어내는 방식을 사용한다.
• 동적 프로그래밍으로 풀 수 있는 가장 유명한 문제로 배낭 문제(Knapsack problem)를 들 수 있다.
• 이것만 살펴보면 DP를 쉽게 이해할 수 있다.

이제 DP에 대한 개념을 어느정도 알아 보았으니 관련된 문제를 풀어보았다.

#include <iostream>
#include <vector>

std::vector<int> dp_vector;
int X;
int result;

void output()
{
	std::cout << result;
}

void solution()
{
	dp_vector[1] = 0;
	for (int i = 2 ; i <= X ; i++)
	{
		dp_vector[i] = dp_vector[i - 1] + 1;
		if (i % 2 == 0)
			dp_vector[i] = std::min(dp_vector[i],dp_vector[i / 2] + 1);
		if (i % 3 == 0)
			dp_vector[i] = std::min(dp_vector[i],dp_vector[i / 3] + 1);
	}
	result = dp_vector[X];
}

void input()
{
	std::cin >> X;
	dp_vector.resize(X + 1);
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}