숫자 맞추기

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

13392번 문제인 방법을 출력하지 않는 숫자 맞추기 문제에 백트래킹만 추가해주면 되는 문제이다.

상세한 풀이는 13392번 문제의 풀이를 참고하도록 하자.

그래도, 아무것도 안 적어놓기는 멋쩍으니 아래와 같이 풀이를 적어 놓는다.

Top-down DP를 활용하면 되고, 아래와 같이 CACHE를 정의해준다.

• CACHE[i][j]: i-1번 숫자 나사까지는 모두 맞춰놓았고, 이때까지 사용한 좌회전 수가 j일 때, 남은 숫자 나사들(i ~ N)을 맞추기 위해 필요한 최소한의 이동 횟수

CACHE[i][j]를 구할 때, j를 활용해서 현재 i번 숫자 나사의 상태를 알 수 있다.

i번 나사를 좌회전 하는 경우, 우회전 하는 경우로 나누어 재귀 호출을 통해 DP를 진행해준다.

완성된 DP 테이블을 사용하여 DP 테이블을 구성했던 것과 유사하게 백트래킹을 진행해준다.

#include <cstdio>
#include <algorithm>

using namespace std;

const int kMaxN = 10000;
const int kNumOfDigits = 10;

int SRC[kMaxN + 1];
int DST[kMaxN + 1];

int N;
int CACHE[kMaxN + 1][kNumOfDigits];

void Initialize()
{
  for (int i = 0; i < kMaxN + 1; ++i)
  {
    for (int j = 0; j < kNumOfDigits; ++j)
    {
      CACHE[i][j] = -1;
    }
  }
}

int Solve(const int screw_idx, const int left_turn)
{
  if (screw_idx > N)
  {
    return 0;
  }

  int& ret = CACHE[screw_idx][left_turn];
  if (ret != -1)
  {
    return ret;
  }

  int current = (SRC[screw_idx] + left_turn) % kNumOfDigits;
  int target = DST[screw_idx];

  int lmove = ((target - current) + kNumOfDigits) % kNumOfDigits;
  int rmove = ((current - target) + kNumOfDigits) % kNumOfDigits;

  ret = min(lmove + Solve(screw_idx + 1, (left_turn + lmove) % kNumOfDigits), rmove + Solve(screw_idx + 1, left_turn));

  return ret;
}

void Backtrack(const int screw_idx, const int left_turn)
{
  if (screw_idx > N)
  {
    return;
  }

  int current = (SRC[screw_idx] + left_turn) % kNumOfDigits;
  int target = DST[screw_idx];

  int lmove = ((target - current) + kNumOfDigits) % kNumOfDigits;
  int rmove = ((current - target) + kNumOfDigits) % kNumOfDigits;

  int left_chosen = lmove + Solve(screw_idx + 1, (left_turn + lmove) % kNumOfDigits);
  int right_chosen = rmove + Solve(screw_idx + 1, left_turn);

  if (left_chosen < right_chosen)
  {
    printf("%d %d\n", screw_idx, lmove);
    Backtrack(screw_idx + 1, (left_turn + lmove) % kNumOfDigits);
  }
  else
  {
    printf("%d %d\n", screw_idx, -rmove);
    Backtrack(screw_idx + 1, left_turn);
  }

  return;
}

int main(void)
{
  // Read Inputs
  scanf(" %d", &N);
  for (int i = 1; i <= N; ++i)
  {
    scanf(" %1d", &SRC[i]);
  }
  for (int i = 1; i <= N; ++i)
  {
    scanf(" %1d", &DST[i]);
  }

  // Initialize
  Initialize();

  // Print total movements
  printf("%d\n", Solve(1, 0));

  // Print backtracking
  Backtrack(1, 0);

  return 0;
}