백준 알고리즘 1463
이번 문제는 DP(Dynamic Programing)문제였다. 이전에 DP에 대한 이해를 하고 문제를 푼 적이 없어서 문제를 풀기 전에 간단하게 DP에 대해 알아보았다. 출처는 아래의 Blog이다.
•
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();
}
C++
복사
