2494 숫자 맞추기 https://www.acmicpc.net/problem/2494
1. 자물쇠
길이 N인 자물쇠가 주어진다.
자물쇠는 최대3칸, 최대 3개의 인접한 디스크를 돌릴 수 있다.
자물쇠를 최소한으로 돌려 맞출 수 있는 횟수를 구하는 문제이다.
한달전에는 못푼문제라 다시 풀게 되었다.
시계방향으로 통일(반시계방향값은 시계방향으로 변환 -3 -> +7)하여 그냥 dp로 풀면 된다.
한번 WA가 나왔는데 현재 위치의 자물쇠번호가 일치할때는 바로 밑 과정은 생략하고 다음 위치로 이동시켰는데 반례가 있는 듯하다.
찾지는 못했다...
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N;
int dp[10][10][10][104];
int in[101], out[101];
int change(int x) {
if (x < 0) return (10 - ((-x) % 10)) % 10;
else return x % 10;
}
int solve(int a, int b, int c, int num) {
if (num == N) return 0;
int &ret = dp[a][b][c][num];
if (ret != -1) return ret;
ret = INF;
if (change(in[num] + a) == out[num])
ret = solve(b, c, 0, num + 1); // AC
// return ret = solve(b, c, 0, num + 1); // WA
for (int n = -3; n <= 3; n++) {
if (n == 0) continue;
int na = change(a + n);
int nb = change(b + n);
int nc = change(c + n);
ret = min(ret, solve(na, b, c, num) + 1);
ret = min(ret, solve(na, nb, c, num) + 1);
ret = min(ret, solve(na, nb, nc, num) + 1);
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0; n < N; n++)
scanf("%1d", &in[n]);
for (int n = 0; n < N; n++)
scanf("%1d", &out[n]);
printf("%d\n", solve(0, 0, 0, 0));
return 0;
}
| cs |
2. 숫자 맞추기
비슷한 문제다.
현재 자물쇠의 번호에 따라서만 결정된다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
int in[10001], out[10001];
int dp[10][10001];
int solve(int cnt, int idx) {
if (idx == N) return dp[cnt][idx] = 0;
int &ret = dp[cnt][idx];
if (ret != -1) return ret;
int diff = (out[idx] + 10 - (in[idx] + cnt) % 10) % 10;
if (diff == 0) ret = solve(cnt, idx + 1);
else {
int pd = diff > 0 ? diff : 10 - diff;
int md = 10 - pd;
ret = min(solve((cnt + pd) % 10, idx + 1) + pd, solve(cnt, idx + 1) + md);
}
return ret;
}
void reconstruct(int cnt, int idx) {
if (idx == N) return;
int diff = (out[idx] + 10 - (in[idx] + cnt) % 10) % 10;
if (diff == 0) reconstruct(cnt, idx + 1);
else {
int pd = diff > 0 ? diff : 10 - diff;
int md = 10 - pd;
if (solve((cnt + pd) % 10, idx + 1) + pd <= solve(cnt, idx + 1) + md) {
printf("%d %d\n", idx + 1, pd);
reconstruct((cnt + pd) % 10, idx + 1);
}
else {
printf("%d %d\n", idx + 1, -md);
reconstruct(cnt, idx + 1);
}
}
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%1d", &in[n]);
for (int n = 0;n < N;n++) scanf("%1d", &out[n]);
printf("%d\n",solve(0, 0));
reconstruct(0, 0);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기