(2494) 숫자 맞추기

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

단계별로 풀어보기

50단계(동적 계획법 4) 4번째

 

 

 

이전 문제와 똑같지만 역추적으로 정답 과정까지 구해야 하는 문제.

DP를 역추적할 때 prev배열을 만들거나 하는 방법이 있지만, 별도의 기록 없이 역추적이 가능하기도 하다.

DP 식을 max나 min 등을 이용해 갱신하는 방식으로 채웠다면 이전 단계에서의 상태를 전부 살펴보며 점화식의 등식이 역으로 성립하는 경우를 찾으면 된다.

 

참고로 이 문제에서 어떤 나사를 왼쪽으로 a번, 오른쪽으로 b번 돌렸다면 그냥 그 나사를 a-b번 돌리고 그 아래 나사를 a번 돌리면 되므로 최적해에서 어떤 나사는 항상 왼쪽이나 오른쪽으로만 돌아간다. 이를 이용하면 DP 연산도 20N번만에 할 수 있고, 역추적도 더 쉽게 가능하지만 귀찮아서 그냥 나이브한 방법을 썼다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 1000001

int main() {
  int n;
  string a, b;
  
  cin >> n >> a >> b;
  
  vector dp(n+1, vector<int> (10, INF)), prev(n+1, vector<int> (10));
  
  dp[0][0]= 0;
  
  for(int i=0;i<n;i++){
    for(int j=0;j<10;j++){
      for(int k=0;k<10;k++){
        int val= dp[i][k]+(j+10-k)%10+(a[i]+j-b[i]+10)%10;
        
        if(dp[i+1][j]>val){
          dp[i+1][j]= val;
          prev[i+1][j]= k;
        }
      }
    }
  }
  
  int now= 0;
  vector<int> res(n);
  
  for(int i=0;i<10;i++){
    if(dp[n][now]>dp[n][i])  now= i;
  }
  
  cout << dp[n][now] << "\n";
  
  for(int i=n-1;i>=0;i--){
    for(int j=0;j<10;j++){
      if(dp[i+1][now]==dp[i][j]+(now+10-j)%10+(a[i]+now-b[i]+10)%10){
        res[i]= (now+10-j)%10 ? (now+10-j)%10 : -(a[i]+now-b[i]+10)%10;
        now= j;
        
        break;
      }
    }
  }
  
  for(int i=0;i<n;i++){
    cout << i+1 << " " << res[i] << "\n";
  }
  
  return 0;
}