[백준 / C++] 12852번 1로 만들기 2

문제 재정의 및 추상화

결론: 주어진 수를 3으로 나누거나, 2로 나누거나, 1을 빼서 1로 만들 때, 최종 연산 횟수와 그 연산 과정에 있는 수들을 구하라.

문제 접근 방식

• 시간 제한은 매우 짧고, 계산 할 것은 매우 많다.
  -> 동적 계획법을 써보자.
• 백준에 있는 1로 만들기 문제와 같으나, 연산 과정에서 포함된 수를 구하는 것이 추가되었다.
  -> 역추적을 추가해보자!

해법을 찾는데 결정적이었던 깨달음

📌 dp[i] = dp[i - 1] + 1 || dp[i / 2] +1 || dp[i / 3] +1

dp[i] 는 i 를 1로 만드는데 드는 최소 연산 횟수를 의미하며, track[i] 는 i 이전의 숫자를 저장하는 역추적 배열이다.

3으로 나누었든, 2로 나누었든, 1을 뺐든, 그 이전의 dp값에서 한 번의 연산의 추가되었다는 의미의 점화식이다.

문제 풀이 로직

1. 자연수 n을 입력받는다.
2. dp[1]을 0으로 초기화한다.
3. track[1]을 경로가 존재하지 않는다는 의미의 1로 초기화한다.
4. 2부터 n까지 돌며 아래를 반복한다.
   4-1. 기본적으로 dp[i] = dp[i - 1] + 1이고, track[i] = i - 1이다.
   4-2. 만약 2로 나누어 떨어지고 그 연산값이 최솟값이라면 2로 나누는 데에 해당하는 dp와 track 식을 써준다.
   4-3. 만약 3으로 나누어 떨어지고 그 연산값이 최솟값이라면 3으로 나누는 데에 해당하는 dp와 track 식을 써준다.
5. 최소 연산 횟수인 dp[n]을 출력한다.
6. n이 0이 아니면 n부터 출력하고, n이 1이 아닐 때 까지 track[n] 값도 출력해준다.
   
   

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1000001];
int track[1000001];

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    
    cin >> n;
    
    dp[1] = 0;
    track[1] = 1;
    
    for(int i =2; i <= n; i++){
        dp[i] = dp[i - 1] + 1;
        track[i] = i - 1;
        
        if(i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
            dp[i] = dp[i / 2] + 1;
            track[i] = i / 2;
        }
        
        if(i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
            dp[i] = dp[i / 3] + 1;
            track[i] = i / 3;
        }
    }

    cout << dp[n]<< "\n";
    
    if(n != 0) cout << n << " ";
    
    while(n != 1){
        cout << track[n] << " ";
        n = track[n];
    }

    return 0;
}