(12852) 1로 만들기 2

https://www.acmicpc.net/problem/12852

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 1번째

 

 

 

이제 단순히 동적 계획법으로 답을 구할 뿐만 아니라 중간 과정까지 구해야 한다.

따라서 경로를 역추적하는 배열을 추가로 만들어 dp값이 갱신될 때마다 직전 경로를 저장한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  int n;
  
  cin >> n;
  
  vector<int> dp(n+1, 100001), from(n+1);
  
  dp[1]= 0;
  
  for(int i=1;i<n;i++){
    if(dp[i+1]>dp[i]+1){
      dp[i+1]= dp[i]+1;
      from[i+1]= i;
    }

    if(3*i<=n && dp[3*i]>dp[i]+1){
      dp[3*i]= dp[i]+1;
      from[3*i]= i;
    }
    
    if(2*i<=n && dp[2*i]>dp[i]+1){
      dp[2*i]= dp[i]+1;
      from[2*i]= i;
    }
  }
  
  cout << dp[n] << "\n";
  
  while(n){
    cout << n << " ";
    
    n= from[n];
  }
  
  return 0;
}