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

12852번: 1로 만들기 2

dfs + 백트래킹 기법을 사용해서 푼 문제

 

vector<int> temp  :  dfs를 돌면서 거쳐온 숫자가 순서대로 저장되어 있는 벡터 (경로 저장)

solve 함수의 cnt는 현재 사용된 연산의 횟수

 

solve함수가 실행 될 때마다 현재 숫자 n을 경로벡터(temp)에 저장해 주고

n == 1 이 되면 현재 결과 값과 비교해서 cnt값이 더 작다면 지금까지 지나온 경로를 ret 벡터에 넣어준다

 

모든 경로를 탐색하는게 기본 동작이지만 if(cnt > result) return; 코드가 있기 때문에

현재 구해진 결과값보다 지금 경로에서의 연산 사용횟수가 많아진다면 return을 해서 시간을 줄일 수 있다

#include <bits/stdc++.h>
 
using namespace std;
 
int result = 999999;
vector<int> temp, ret;
 
void solve(int n, int cnt){
    if(cnt > result) return;
    if(n == 1){
        if(cnt < result){
            result = cnt;
            temp.push_back(n);
            ret = temp;
            temp.pop_back();
        }
        return;
    }
 
    temp.push_back(n);
    
    if(n % 3 == 0) solve(n/3, cnt+1);
    if(n % 2 == 0) solve(n/2, cnt+1);
    solve(n-1, cnt+1);
    
    temp.pop_back();
}
 
int main(){
    int N;
    cin >> N;
    solve(N, 0);
    cout << result << "\n";
    for(auto w : ret){
        cout << w << " ";
    }
    return 0;
}