문제 설명
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오
https://www.acmicpc.net/problem/12852
제한 사항


풀이
문제를 요약하면 N이 주어지면 최소한의 연산으로 N을 1로 만드는 방법을 찾는 것이다.
이때 가능한 연산은 다음과 같다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
해당 문제는 dp를 쓰면 간단하게 해결할 수 있다.
N부터 시작으로 위의 연산을 수행할 수 있는지 확인하고 가능하다면 연산의 개수를 세며 최소한의 연산으로 다음 수를 만들 수 있는지 확인하면 된다.
예를 들어 N이 9라고 해보자.
9는 3으로 나누어 떨어지므로 9에서 9/3을 만들 수 있다.
따라서 다음과 같은 식을 적용할 수 있다.
dp[i / 3] = { dp[i].first + 1, DIV3 };
dp에 기록하는 값은 2가지인데 하나는 연산의 횟수이고 다른 하나는 어떠한 연산으로 i번째 수를 만들었는지 기록한다.
이는 연산과정을 추적하기 위함이다.
N부터 1까지 이런 과정을 진행하면 dp[1]에는 N에서 1을 만들기 위한 최소의 연산 수가 기록되어 있을 것이다.
또한, 1을 만든 연산이 second에 기록되어 있을 것이므로 이를 역으로 적용하면 이전 수를 찾을 수 있다.
이를 반복하다 N을 만들게 되면 모든 과정을 추적한 것이다.
int temp = 1;
vector<int> result;
while (temp != N)
{
result.push_back(temp);
if (dp[temp].second == DIV3) temp *= 3;
else if (dp[temp].second == DIV2) temp *= 2;
else if (dp[temp].second == MINUS) temp++;
}
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
int N;
enum Operate
{
None,
DIV3,
DIV2,
MINUS,
};
vector<pair<int,int>> dp;
const int MAX = 987654321;
int main()
{
INPUT_OPTIMIZE;
cin >> N;
dp.resize(N + 1, { MAX , None });
dp[N] = { 0, None };
for (int i = N; i > 0; i--)
{
if (i % 3 == 0)
{
if (dp[i / 3].first > dp[i].first + 1)
{
dp[i / 3] = { dp[i].first + 1, DIV3 };
}
}
if (i % 2 == 0)
{
if (dp[i / 2].first > dp[i].first + 1)
{
dp[i / 2] = { dp[i].first + 1, DIV2 };
}
}
if (dp[i - 1].first > dp[i].first + 1)
{
dp[i - 1] = { dp[i].first + 1, MINUS };
}
}
cout << dp[1].first << "\n";
int temp = 1;
vector<int> result;
while (temp != N)
{
result.push_back(temp);
if (dp[temp].second == DIV3) temp *= 3;
else if (dp[temp].second == DIV2) temp *= 2;
else if (dp[temp].second == MINUS) temp++;
}
cout << N << " ";
while (!result.empty())
{
cout << result.back() << " ";
result.pop_back();
}
return 0;
}