이번에는 백준 12852번 1로 만들기 2 문제를 풀어보았습니다.
정수 N을 1로 만들기 위해 사용할 수 있는 연산은 3가지입니다.
- 3으로 나누어 떨어지면 3으로 나누기
- 2로 나누어 떨어지면 2로 나누기
- 1 빼기
최소 연산 횟수를 구하는 것뿐만 아니라, 실제로 N에서 1까지 어떤 수들을 거쳐가는지도 출력해야 합니다.
dp[i]에 i를 1로 만드는 최소 연산 횟수를 저장하고, 계산이 끝난 뒤 DP 값의 관계를 이용하여 경로를 역추적하는 방식으로 해결하였습니다.
문제 설명
정수 N이 주어졌을 때 다음 세 가지 연산을 사용할 수 있습니다.
1. 3으로 나누어 떨어지면 3으로 나누기
2. 2로 나누어 떨어지면 2로 나누기
3. 1 빼기이 연산들을 적절하게 사용하여 N을 1로 만들어야 합니다.
이때 출력해야 하는 것은
최소 연산 횟수
N → ... → 1로 이동하는 실제 경로입니다.
풀이 아이디어
dp[i]를 다음과 같이 정의합니다.
dp[i] = i를 1로 만드는 데 필요한 최소 연산 횟수1은 이미 1이므로
dp[1] = 0;으로 시작합니다.
이후 2부터 N까지 순서대로 DP를 채웁니다.
현재 숫자가 i라면 가능한 이전 상태는 다음과 같습니다.
i / 3
i / 2
i - 1물론 나누기는 실제로 나누어 떨어지는 경우에만 사용할 수 있습니다.
따라서
if (i%3 == 0) dp[i] = min(dp[i/3] + 1, dp[i]);
if (i%2 == 0) dp[i] = min(dp[i/2] + 1, dp[i]);
dp[i] = min(dp[i-1] + 1, dp[i]);와 같이 최솟값을 저장합니다.
이렇게 최소 횟수를 모두 구한 뒤, N부터 시작해서
dp[next] + 1 == dp[current]을 만족하는 다음 숫자로 이동하면 실제 최단 경로를 복원할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int dp[1000004];
void solve(int n) {
if (n == 0) return;
cout << n << ' ';
if (n%3 == 0 && dp[n/3] + 1 == dp[n]) solve(n/3);
else if (n%2 == 0 && dp[n/2] + 1 == dp[n]) solve(n/2);
else if (n > 1 && dp[n-1] + 1 == dp[n]) solve(n-1);
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
fill(dp, dp+1000004, INT_MAX);
dp[1] = 0;
for (int i=2; i<=n; i++) {
if (i%3 == 0) dp[i] = min(dp[i/3] + 1, dp[i]);
if (i%2 == 0) dp[i] = min(dp[i/2] + 1, dp[i]);
dp[i] = min(dp[i-1] + 1, dp[i]);
}
cout << dp[n] << '\n';
solve(n);
return 0;
}풀이 흐름
-
dp배열을INT_MAX로 초기화합니다. -
dp[1] = 0으로 설정합니다. -
2부터N까지 순서대로 DP를 계산합니다. -
현재 숫자가 3으로 나누어 떨어진다면
dp[i/3] + 1을 확인합니다. -
2로 나누어 떨어진다면
dp[i/2] + 1을 확인합니다. -
항상 사용할 수 있는
dp[i-1] + 1도 확인합니다. -
세 경우 중 가장 작은 값을
dp[i]에 저장합니다. -
dp[N]을 출력하면 최소 연산 횟수를 구할 수 있습니다. -
이후
solve(N)을 호출합니다. -
현재
n에서 가능한 다음 숫자 중dp[next] + 1 == dp[n]을 만족하는 값을 선택합니다. -
같은 과정을 반복하여 1까지 경로를 출력합니다.
구현 포인트
1. DP의 의미
int dp[1000004];dp[i]는
i에서 1까지 가기 위한 최소 연산 횟수를 의미합니다.
예를 들어
dp[1] = 0
dp[2] = 1
dp[3] = 1입니다.
2는 한 번 2로 나누면 1이 되고, 3 역시 한 번 3으로 나누면 1이 됩니다.
2. DP 초기화
fill(dp, dp+1000004, INT_MAX);최솟값을 구해야 하므로 처음에는 모든 값을 매우 큰 값으로 초기화합니다.
이후 가능한 연산을 확인하면서 더 작은 값으로 갱신합니다.
3. 시작 상태
dp[1] = 0;1은 이미 목표 숫자이므로 아무 연산도 필요하지 않습니다.
따라서 최소 연산 횟수는 0입니다.
이 값이 이후 DP 계산의 시작점이 됩니다.
4. 3으로 나누는 경우
if (i%3 == 0) dp[i] = min(dp[i/3] + 1, dp[i]);현재 숫자가 3으로 나누어 떨어진다면
i → i / 3으로 이동할 수 있습니다.
i / 3에서 1까지 가는 최소 연산 횟수가 이미 dp[i/3]에 저장되어 있으므로, 현재 한 번의 연산을 추가하면
dp[i/3] + 1이 됩니다.
5. 2로 나누는 경우
if (i%2 == 0) dp[i] = min(dp[i/2] + 1, dp[i]);2로 나누어 떨어지는 경우에도 같은 방식입니다.
i → i / 2로 한 번 이동하고, 이후 필요한 최소 연산 횟수를 더합니다.
따라서 후보 값은
dp[i/2] + 1입니다.
6. 1을 빼는 경우
dp[i] = min(dp[i-1] + 1, dp[i]);1을 빼는 연산은 어떤 숫자에서도 사용할 수 있습니다.
따라서
i → i - 1로 이동한 뒤 i-1에서 1까지 가는 최소 횟수를 더하면 됩니다.
후보 값은
dp[i-1] + 1입니다.
7. 왜 작은 숫자부터 계산하는가
for (int i=2; i<=n; i++)현재 dp[i]를 계산할 때 필요한 값은
dp[i/3]
dp[i/2]
dp[i-1]입니다.
이 값들은 모두 i보다 작은 숫자입니다.
따라서 2부터 증가하는 순서로 계산하면 필요한 DP 값들이 항상 미리 계산되어 있습니다.
8. 최소 연산 횟수 구하기
현재 숫자 i에서 가능한 모든 경우를 확인하고 그중 가장 작은 값을 저장합니다.
결국 점화식은 다음과 같이 볼 수 있습니다.
dp[i] = dp[i-1] + 1을 기본으로 두고,
i % 2 == 0 → dp[i/2] + 1
i % 3 == 0 → dp[i/3] + 1도 비교합니다.
따라서 dp[N]에는 N을 1로 만드는 최소 연산 횟수가 저장됩니다.
9. 경로 복원
이 문제에서는 최소 연산 횟수뿐만 아니라 실제 경로도 출력해야 합니다.
이를 위해
void solve(int n)함수를 사용하였습니다.
현재 숫자를 먼저 출력합니다.
cout << n << ' ';이후 DP 관계를 이용하여 다음 숫자를 결정합니다.
10. 3으로 나눈 경로 확인
if (n%3 == 0 && dp[n/3] + 1 == dp[n])
solve(n/3);n이 3으로 나누어 떨어지고
dp[n/3] + 1 == dp[n]이라면 현재 최단 경로에서 3으로 나누는 연산을 선택해도 된다는 뜻입니다.
예를 들어
dp[9] = 2
dp[3] = 1이라면
dp[3] + 1 = dp[9]이므로
9 → 3은 최단 경로에 포함될 수 있습니다.
11. 2로 나눈 경로 확인
else if (n%2 == 0 && dp[n/2] + 1 == dp[n])
solve(n/2);3으로 나누는 경로가 선택되지 않았다면 2로 나누는 경우를 확인합니다.
마찬가지로
dp[n/2] + 1 == dp[n]이라면 해당 연산을 사용했을 때 최소 횟수를 유지할 수 있습니다.
12. 1을 빼는 경로 확인
else if (n > 1 && dp[n-1] + 1 == dp[n])
solve(n-1);앞의 두 경우가 아니라면 1을 빼는 경로를 확인합니다.
dp[n-1] + 1 == dp[n]이라면
n → n-1로 이동하는 것이 최단 경로에 포함됩니다.
13. dp 관계만으로 경로를 찾을 수 있는 이유
현재 숫자가 n이고
dp[n] = k라고 하겠습니다.
최단 경로에서 다음 숫자로 이동했다면 그 숫자에서는 정확히 k-1번의 연산만 필요해야 합니다.
따라서 다음 상태 next는 반드시
dp[next] + 1 == dp[n]을 만족합니다.
이 조건을 이용하면 별도의 이전 위치 배열을 저장하지 않아도 실제 최단 경로를 복원할 수 있습니다.
14. 정답이 여러 개여도 상관없는 이유
문제에서는 최단 경로가 여러 개라면 아무거나 출력해도 됩니다.
코드에서는 우선순위를
3으로 나누기
→ 2로 나누기
→ 1 빼기순서로 확인합니다.
if (...)
else if (...)
else if (...)구조이기 때문에 여러 최단 경로가 존재하더라도 가장 먼저 조건을 만족한 경로 하나만 선택합니다.
문제에서는 아무 최단 경로나 출력하면 되므로 문제가 없습니다.
15. 전체 로직 정리
전체 흐름은 다음과 같습니다.
dp[1] = 0
↓
2부터 N까지 DP 계산
↓
/3, /2, -1 중 최소 횟수 선택
↓
dp[N] = 최소 연산 횟수
↓
N에서부터 경로 복원
↓
dp[next] + 1 == dp[current]인 상태 선택
↓
1까지 반복즉,
DP → 최소 연산 횟수 계산
재귀 → 실제 최단 경로 복원으로 역할을 나누어 해결하였습니다.
시간복잡도
2부터 N까지 각 숫자를 한 번씩 확인합니다.
각 숫자에서는
3으로 나누기
2로 나누기
1 빼기최대 세 가지 경우만 확인하므로 DP 계산의 시간복잡도는
O(N)입니다.
경로 복원 과정에서도 최대 N개의 숫자를 방문할 수 있으므로 O(N)입니다.
따라서 전체 시간복잡도는
O(N)입니다.
dp 배열에 N개의 값을 저장하므로 공간복잡도는
O(N)입니다.
