(13392) 방법을 출력하지 않는 숫자 맞추기

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

단계별로 풀어보기

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

 

 

 

나사를 왼쪽으로 돌리는 횟수가 위쪽의 나사에 영향을 끼치므로, 이 값을 DP테이블에 기록해야 한다.

DP[a][b]를 a번째 숫자까지 맞추고 왼쪽으로 나사를 돌린 횟수의 일의 자리가 b일 때 이동 최소값이라고 하자.

이때 DP[a+1][c]를 일의 자리가 b에서 c가 될 때까지 나사를 왼쪽으로 돌리고, 목표 숫자와 맞을 때까지 나사를 오른쪽으로 돌린 횟수값과 비교하면 된다.

DP 정의나 점화식에 따라 for문 하나를 줄여 100N번이 아닌 10N번만 연산해서 답을 구할 수도 있지만 이 정도도 충분히 시간 내 통과할 수 있기 때문에 개인적으로 가장 직관적인 점화식을 선택했다.

 

 

 

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

int main() {
  int n, ans= INF;
  string a, b;
  
  cin >> n >> a >> b;
  
  vector dp(n+1, vector<int> (10, INF));
  
  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++){
        dp[i+1][j]= min(dp[i+1][j], dp[i][k]+(j+10-k)%10+(a[i]+j-b[i]+10)%10);
      }
    }
  }
  
  for(int i=0;i<10;i++)  ans= min(ans, dp[n][i]);
  
  cout << ans;
  
  return 0;
}