https://www.acmicpc.net/problem/1463
문제
> 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
> 정수 N이 주어질 때, 위 연산을 사용해 1을 만드고자 할 때 연산의 최솟값을 구해라.접근
dp(Dynamic programming)를 사용해서 문제를 해결하면 된다.
DP(Dynamic programming)
> DP는 동적프로그래밍으로 "큰 문제를 작은 문제로 나누고, 그 결과를 기억해놓고 중복계산을 피하며 다시 큰 문제를 해결할 때 사용하는 방법이다.
> DP를 사용하기 위해선 두 가지 조건을 만족해야한다.
1. Overlapping Subproblems - 겹치는 부분 문제
-> DP는 문제를 나누고 그 결과를 재활용해서 전체의 답을 구하는 구조이다.
그래서 동일한 작은 문제들, 겹치는 부분이 반복적으로 나타나는 경우에 사용이 가능하다.
2. Optimal Substructure - 최적 부분 구조
-> 부분 문제의 최적의 결과 값을 사용해 전체 문제의 최적의 결과를 낼 수 있는 경우를 의미한다. DP연산을 보면 작은 경우 부터 각각의 최단,최소 경로를 구해 합쳐 결과를 내기 때문이다.문제해결
> DP의 값을 저장할 벡터를 선언한다. 크기는 인덱스는 0부터 이기 때문에 +1을 해준다. 각 dp연산 뒤에 +1은 dp[i]에서 dp[i-1], dp[i/2] 등 해당 연산의 값을 얻기 위해 한 번 연산을 했기 때문에 더해준다.(dp[10] = dp[9] +1, 10에서 9로 바뀌기 위해 한번 연산 했기 때문에)
> dp[1]은 이미 1이라 0이므로 제외하고 2부터 시작한다.
> 2, 3으로 나누어 떨어질땐 조건부이기 때문에 1을 뺏을 때를 기준으로 잡기 위해서 먼저해준다.
> 나온 값과 각각 2, 3으로 나누어 떨어질 때의 경우와 비교해 min연산으로 최소의 경우를 누적한다.
> N까지 연산하고 최종 값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
int cnt = 0;
cin >> N;
vector<int> dp(N + 1, 0);
for (int i = 2; i <= N; i++)
{
dp[i] = dp[i - 1] + 1;
if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
}
cout << dp[N] << '\n';
}
후기
처음 문제를 보고 아무 생각도 나지 않았지만 DP를 사용해서 해결하는 문제인걸 알고 DP에 대해 공부했다.
연산 하나하나 이해가 안됐지만 계속 뜯어보고 동작을 확인하고하니 이해 됐다. 알고보니 간단한 알고리즘이고 편리했다.
