| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1658 | 484 | 349 | 32.956% |
문제
아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10개의 면을 가지고 있고, 각 면에는 오른쪽 방향으로 0, 1, 2, 3, …, 9까지의 숫자가 하나씩 순서대로 적혀 있다. 하나의 숫자나사를 왼쪽으로 회전 시키면, 이 나사보다 아래에 위치한 모든 나사는 같이 따라서 돌게 되지만, 나사를 오른쪽으로 회전시키면, 다른 나사는 함께 돌지는 않는다. 정면에서 보아 위에서부터 아래쪽으로 숫자를 읽어 내려간다고 할 때, 현재의 상태에서 가장 적은 칸수의 움직임으로 원하는 숫자를 만들기 위한 방법을 출력하는 프로그램을 작성하라.
예를 들어 세 개의 숫자나사가 주어졌을 때, 정면에서 보는 현재 상태가 326이고 원하는 상태는 446이라면 최소 회전 칸수는 4이다. 먼저 숫자나사 1을 왼쪽으로 한 칸 돌리면 437이 되고, 숫자나사 2를 역시 왼쪽으로 한 칸 돌리면 448이 되며, 마지막으로 숫자나사 3을 오른쪽으로 두 칸 돌리면 446이 된다.
입력
첫째 줄에는 숫자나사의 개수 N이 주어지고, 둘째 줄에는 현재의 상태가, 셋째 줄에는 원하는 상태가 주어진다. N은 3 이상이고 10,000 이하이다.
출력
첫째 줄에는 현재 상태에서 원하는 상태로 도달하는데 필요한 최소 회전 칸수를 출력한다. 다음 줄부터는 회전 순서대로 각 줄에 하나의 숫자나사 번호와 회전 칸수를 빈칸을 사이에 두고 출력한다. 회전 칸수는 왼쪽을 기준으로 하여 출력한다. 만일 왼쪽으로 4칸 회전한다면 4를, 오른쪽으로 3칸 회전한다면 -3을 출력한다. 답이 여러 개이면 그 중에 하나만 출력한다.
접근
생각보다 까다롭고 귀찮은 DP 문제였다.
DP 테이블은 간단하게 나오는데, table[i][j] = i번째 나사가 왼쪽으로 j번 돌아간 상태이다.
초기값을 큰 값으로 설정해놓고, table마다 해당 상태의 최솟값을 넣어놓으면 된다.
i번째 인덱스는, table[i - 1][j]에서 j를 0부터 9까지 순회한다.
각 j 상태에서 왼쪽, 오른쪽으로 원하는 결과만큼 간 이후의 2번째 차원을 계산해주면 된다.
왼쪽으로 가면 dp[i][(j + 왼쪽으로 간 횟수) % 10] 테이블을 갱신해주고,
오른쪽을 가면 dp[i][j] 테이블을 갱신해주면 된다.
그리고 갱신될 때 마다 이전 상태와 움직인 횟수를 저장해서 출력에 용이하게 해준다.
풀이
구현이 굉장히 귀찮은 문제였다.
dp[i][j] = i번째가 왼쪽으로 j번 돌아가 있을 때의 최솟값
before[i][j] = dp[i][j]에 오기 이전 {dp[i-1]일 때의 j, 이번에 돌아간 횟수}
Print[i] = i번째 나사가 돌아간 횟수(마지막에 reverse 출력용)
으로 배열들을 놓았다.
그리고 0번째 나사를 각 왼쪽, 오른쪽으로 돌려주고 값을 넣어주었다.
이 후 1부터 N - 1번째 나사까지 돌아가면서 정의한 점화식을 넣어줬다.
l은 이번 나사가 왼쪽으로 돌아서 정답이 되는 횟수, r은 오른쪽이다.
그리고 j 와 l을 이용해서 실제로 회전해야하는 횟수 move_l, move_r을 구해줬다.
테이블을 다 채우고 나면 최솟값을 찾아가면서 Print 배열을 채워넣는다.
그리고 다시 0부터 순회하면서 출력해주면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
const int INF = 1e9;
int N, dp[10000][10], arr[10000], ans[10000], l, r, Print[10000];
pair<int, int> before[10000][10]; // {전 j 인덱스, 움직임}
string A, B;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(N);
CIN2(A, B);
FUP(i, 0, N - 1)
{
arr[i] = A[i] - '0';
ans[i] = B[i] - '0';
FUP(j, 0, 9) dp[i][j] = INF;
}
int first_l = (ans[0] + 10 - arr[0]) % 10;
int first_r = (10 - first_l) % 10;
dp[0][first_l] = first_l;
dp[0][0] = first_r;
FUP(i, 1, N - 1)
{
l = (ans[i] + 10 - arr[i]) % 10;
r = (10 - l) % 10;
FUP(j, 0, 9)
{
if (dp[i - 1][j] == INF) continue;
int move_l = (l + 10 - j) % 10;
int move_r = (r + j) % 10;
if (dp[i][(j + move_l) % 10] > dp[i - 1][j] + move_l)
{
dp[i][(j + move_l) % 10] = dp[i - 1][j] + move_l;
before[i][(j + move_l) % 10] = { j, move_l };
}
if (dp[i][j] > dp[i - 1][j] + move_r)
{
dp[i][j] = dp[i - 1][j] + move_r;
before[i][j] = { j, -move_r };
}
}
}
int j = 0, temp = INF;
FUP(i, 0, 9)
{
if (temp > dp[N - 1][i])
{
j = i;
temp = dp[N - 1][i];
}
}
COUT(temp);
ENDL;
FDOWN(i, N - 1, 1)
{
Print[i] = before[i][j].second;
j = before[i][j].first;
}
Print[0] = j == 0 ? -first_r : first_l;
FUP(i, 0, N - 1)
{
COUT2(i + 1, Print[i]);
ENDL;
}
return 0;
}