사용한 알고리즘
알고리즘 설명
- 먼저 나사의 성질을 확실하게 알아야한다.
- 나사를 왼쪽으로 돌리면 아래에 있는 나사들도 같이 돌아간다.
- 오른쪽으로 돌리면 돌리는 나사만 돌아간다.
- 이는 위쪽에 있는 나사에 따라서 아래쪽 나사들이 연관이 있다는 의미이다.
- 문제 상황을 나누면,
1. 위에서 몇번 왼쪽으로 돌렸는지, 2. 몇번째 나사인지 이 두가지로 나눌 수 있다. - 1번째 상황은 0~9번으로 표현할 수 있다.(10번돌리나 20번돌리나 같은 값)
- 2번째 상황은 총 10000개 이하이다.
- 총 필요한 문제 상황은 10만개로 메모이제이션(memoization)으로 표현할 수 있다.
- DP(i,j): 위에서 i번 왼쪽으로 돌렸을때, j번째~N번째 나사를 모두 맞추기 위해서 돌려야하는 최소 횟수
- 문제 DP를 정의하고 왼쪽으로 돌리는 경우, 오른쪽으로 돌리는 경우 2가지로 나누어 DFS를 진행한다.
- 왼쪽으로 돌려야하는 횟수 = l, 오른쪽으로 돌려야하는 횟수 r
- 점화식: DP(i,j) = min(DP(i+1, j+l)+l, DP(i+1,j)+r)
- 이후에 다시 얼마나 돌려야 하는지는 DP를 이용해서 추적을 하게 된다.
- 구한 점화식으로 각 나사에서 오른쪽으로 돌려 맞춰야 하는지 왼쪽으로 돌려서 맞춰야 하는지를 판단한다.
- 결과를 출력한다.
풀이
// baekjoon 2494 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N=10002;
int N, dp[10][MAX_N];
char S[MAX_N], D[MAX_N];
// here screw and remain turns to left
// 위에서부터 현재 나사 위치 here, 지금까지 왼쪽으로 돌린 횟수 turns
int dfs(int here, int turns) {
// 모든 나사를 맞춘경우
if (here == N) return dp[turns][here]=0;
int &ret = dp[turns][here];
if (ret != -1) return ret;
ret = 1e9; // init
// 나사를 맞추기 위해서 왼쪽으로 돌려야 하는 횟수
int df = (20+((int)(D[here]-'0')-(int)(S[here]-'0'))-turns)%10; // remain to left
// 왼쪽으로 돌리는 경우
ret = min(ret, dfs(here + 1, (df+turns)%10) + df);
// 오른쪽으로 돌리는 경우
ret = min(ret, dfs(here + 1, turns) + (10-df)%10);
return ret;
}
void backTracking(int here, int turns) {
if (here == N) return;
int df = (20+((int)(D[here]-'0')-(int)(S[here]-'0'))-turns)%10; // remain to left
// 오른쪽으로 돌리는 경우
if (dp[turns][here+1] != -1 && dp[turns][here]-dp[turns][here+1] == (10-df)%10) {
printf("%d %d\n", here+1, -(10-df)%10);
backTracking(here+1, turns);
}
// 왼쪽으로 돌리는 경우
else {
printf("%d %d\n", here+1, df);
backTracking(here+1, (10+df+turns)%10);
}
}
int main() {
memset(dp, -1, sizeof(dp));
scanf("%d", &N);
scanf("%s%s", S, D);
printf("%d\n", dfs(0, 0));
backTracking(0, 0);
return 0;
}
