백준 2494: 숫자 맞추기

문제 요약

N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10개의 면을 가지고 있고, 각 면에는 오른쪽 방향으로 0, 1, 2, 3, …, 9까지의 숫자가 하나씩 순서대로 적혀 있다. 하나의 숫자나사를 왼쪽으로 회전 시키면, 이 나사보다 아래에 위치한 모든 나사는 같이 따라서 돌게 되지만, 나사를 오른쪽으로 회전시키면, 다른 나사는 함께 돌지는 않는다. 정면에서 보아 위에서부터 아래쪽으로 숫자를 읽어 내려간다고 할 때, 현재의 상태에서 가장 적은 칸수의 움직임으로 원하는 숫자를 만들기 위한 방법을 출력하는 프로그램을 작성하라.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

사실 이 문제를 보고 바로 dp가 생각이 나지 않았다. 탑다운방식을 통해 해결하려고 했으나, 바텀업 방식과 2차원 dp를 사용하여 해결할 수 있었다.
dp[i][j]에서 i는 0~N번째의 숫자나사이고, j는 나사가 돌아간 정도(0~9)이다.
우선 숫자나사를 위에서부터 맞춰나가야 하는 것은 바로 알 수 있을 것이다. 여기서 첫 나사를 왼쪽으로 돌리느냐와 오른쪽으로 돌리느냐가 갈리는데, 이를 dp로 해결하면 된다.
그렇게 구성한 결과에 최소값과 해당 인덱스를 찾아서 역으로 거슬러 돌린 나사 방향을 알아내면 된다. 스택에 저장해서, 하나씩 꺼내어 출력한다.

틀린 부분은 의외로 간단했는데, cur = (stt[i + 1] - '0' + j) % 10;이다. 10으로 나머지를 구하는 부분을 빼먹어서 계속 틀렸었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#define inf 1000000000

using namespace std;

int n;
string stt, des;
int dp[10001][10];

int main()
{
	int resi, cur, to, res = inf, temp;
	stack<pair<int, int>> s;
	cin >> n >> stt >> des;

	fill(dp[0], dp[10001], inf);

	cur = stt[0] - '0';
	to = des[0] - '0';
	dp[0][0] = cur - to;
	if (dp[0][0] < 0) dp[0][0] += 10;
	temp = to - cur;
	if (temp < 0) temp += 10;
	dp[0][temp] = temp;

	for (int i = 0; i < n - 1; i++) {
		to = des[i + 1] - '0';
		for (int j = 0; j < 10; j++) {
			if (dp[i][j] == inf)
				continue;
			cur = (stt[i + 1] - '0' + j) % 10;

			temp = cur - to;
			if (temp < 0) temp += 10;
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + temp);

			temp = to - cur;
			if (temp < 0) temp += 10;
			dp[i + 1][(j + temp) % 10] = min(dp[i + 1][(j + temp) % 10], dp[i][j] + temp);
		}
	}
	for (int j = 0; j < 10; j++) {
		if (res > dp[n - 1][j]) {
			res = dp[n - 1][j];
			resi = j;
		}
	}

	for (int i = n - 2; i >= 0; i--) {
		to = des[i + 1] - '0';
		for (int j = 0; j < 10; j++) {
			if (dp[i][j] == inf) continue;
			cur = (stt[i + 1] - '0' + j) % 10;
			

			temp = cur - to;
			if (temp < 0) temp += 10;
			if (j == resi && dp[i][j] + temp == dp[i + 1][resi]) {
				if(temp != 0) s.push({i + 2, -temp});
				resi = j;
				break;
			}
			temp = to - cur;
			if (temp < 0) temp += 10;
			if ((j + temp) % 10 == resi && dp[i][j] + temp == dp[i + 1][resi]) {
				if(temp != 0) s.push({ i + 2, temp });
				resi = j;
				break;
			}
		}
	}
	if (resi != 0)		
		s.push({ 1, resi });
	else if(dp[0][resi] != 0)
		s.push({ 1, -dp[0][resi] });
	printf("%d\n", res);
	while (!s.empty()) {
		auto t = s.top();
		printf("%d %d\n", t.first, t.second);
		s.pop();
	}
	return 0;
}