현재 상태의 회전이 가능한 숫자 나사가 주어지고 원하는 상태로 바꿀 때 최소 회전수를 구하는 문제입니다.
숫자 나사를 돌릴 때 왼쪽으로 돌리게 되면 그 나사뿐만 아니라 그 아래에 있는 숫자 나사들까지 같이 왼쪽으로 회전하게 됩니다.
다른 나사까지 움직이지 않았다면 사칙연산 문제가 됐겠지만 그렇지 않으니 다른 방법을 찾아봐야 합니다.
완전 탐색으로 생각했을 때는 숫자 나사 1부터 왼쪽으로 회전해서 원하는 숫자 맞추고 오른쪽으로 회전해서 맞추는 경우를 보고 숫자 나사 2도 똑같이 해보고…. 를 숫자 나사 N까지 하게 되면 시간 복잡도가 O(2^N)입니다.
그런데 왼쪽으로 회전할 경우에만 다른 숫자 나사까지 영향을 주고 나사가 원형이기 때문에 11번을 돌린 결과와 1번을 돌린 결과가 동일한 숫자를 정면에 보입니다.
완전 탐색을 할 경우 위와 같이 중복되는 문제가 있습니다. 중복되는 경우를 줄이면 시간을 줄일 수 있으니 DP로 중복을 제거하겠습니다.
DP[숫자 나사 번호][왼쪽 회전수] = 최소 회전수
before - 돌리기 전 상태 정면 숫자, after - 원하는 정면 숫자
lcnt - 왼쪽 회전수, rcnt - 오른쪽 회전수
전에 왼쪽으로 회전을 했었더라면 지금 숫자 나사도 영향을 받았습니다.
그래서 그걸 감안하여 왼쪽으로 숫자를 돌렸을 경우와 오른쪽으로 돌렸을 경우에 각각 몇 번 돌리는지 저장하겠습니다.
lcnt = (after[번호] - before[번호] - 전 번호 왼쪽 회전수 + 20) % 10
rcnt = 10 - lcnt
after = 0, before = 9일 경우 음수가 나오기 때문에 전 번호 왼쪽 회전수까지 고려하여 20을 더해줘서 양수로 만들고 모듈러 연산을 해줍니다.
필요한 회전 수를 구했으면 왼쪽으로 돌렸을 때와 오른쪽으로 돌렸을 때 최소 회전수를 구할 수 있습니다.
i - 현재 숫자 나사 번호, j - 전 번호 왼쪽 회전 수
오른쪽으로 돌린 경우
DP[i][j] = min(DP[i][j], DP[i-1][j] + rcnt)
왼쪽으로 돌린 경우
DP[i][(j + lcnt) % 10] = min(DP[i][(j + lcnt) % 10], DP[i-1][j] + lcnt)
오른쪽으로 돌릴 경우 왼쪽 회전수는 그대로이니 DP[i-1][j]에 오른쪽 회전수 rcnt를 더한 값을 비교하면 됩니다.
왼쪽으로 돌릴 경우 DP 회전 수에 반영을 해주고 DP[i-1][j]에 왼쪽 회전수 lcnt를 더한 값을 비교하면 됩니다.
이렇게 해서 DP 테이블을 완성하면 DP[N][0] ~ DP[N][9] 중 최솟값이 총 최소 회전수이므로 출력하시면 됩니다.
그림을 보고 좀 무서웠지만 생각보다는 간단한 문제였습니다.
요즘 디피 문제를 자주 풀어서 그런지 점화식 짜는 속도가 빨라지고 있네요 ㅎㅎ
사실 어려운 문제를 피해요…
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
int dp[10005][10];
memset(dp, 0x3f, sizeof(dp));
int a[10005], b[10005], n;
scanf("%d", &n);
FOR(i, 1, n) scanf("%1d", &a[i]);
FOR(i, 1, n) scanf("%1d", &b[i]);
FOR(i, 0, 9) dp[0][i] = i;
FOR(i, 1, n) FOR(j, 0, 9){
int lcnt = (b[i] - j - a[i] + 20) % 10;
int rcnt = 10 - lcnt;
dp[i][j] = min(dp[i][j], dp[i - 1][j] + rcnt);
dp[i][(j + lcnt) % 10] = min(dp[i][(j + lcnt) % 10], dp[i - 1][j] + lcnt);
}
int ans = 1e9;
FOR(i, 0, 9) ans = min(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}