흑 또는 백으로 칠해져있는 N*M 그림이 주어진다.
동호는 흑 또는 백으로 수평으로 칠할 수 있다.
최대 K번 칠할 때 잘못 칠한 부분의 최솟값을 구하는 문제다.
(못 칠한 부분도 잘못 칠한것으로 침)
dp로 [0, 0]에서 시작해서 한행이 끝나면 다음행으로 넘어가서 [N - 1, M - 1]까지
돌리면 되겠다고 생각했다.
약간의 데이터를 만들어서 돌리니 잘 돌아가서 바로제출했다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M, K;
int dp[111][111][3002][2];
char map[101][101];
int sum[101][101];
int get(int y, int x, int state) {
if (map[y][x] == 'W') {
if (state) return 1;
else return 0;
}
else {
if (state) return 0;
else return 1;
}
}
int solve(int y, int x, int cnt, int state) {
if (cnt > K) return INF;
if (x == M) {
if (y == N - 1) return 0;
else return min(solve(y + 1, 0, cnt + 1, 0), solve(y + 1, 0, cnt + 1, 1));
}
int &ret = dp[y][x][cnt][state];
if (ret != -1) return ret;
ret = INF;
ret = min(ret, solve(y, x + 1, cnt, state) + get(y, x, state));
ret = min(ret, solve(y, x + 1, cnt + 1, !state) + get(y, x, state));
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d%d%d", &N, &M, &K);
for (int n = 0;n < N;n++) {
scanf("%s", &map[n]);
int s = 0;
for (int m = 0;m < M;m++) {
if (map[n][m] == 'W') s++;
sum[n][m] = s;
}
}
printf("%d\n", min(solve(0, 0, 1, 0), solve(0, 0, 1, 1)));
return 0;
}
| cs |
Run-time Error
이때 굉장히 몽롱한 상태여서 배열 크기조차 확인을 하지 않았었다.
자고 다시풀기로하고 좀 생각해보니 y축 배열을 크기 2로 줄이고 Sliding window 하듯이
번갈아가면서 bottom up방식으로 바꾸면 메모리 낭비를 줄일 수 있을것 같았다.
이때까지 문제조건을 못본게 있었는데 칠하지 못하는 부분은
잘못칠한것으로 처리한다는 조건이였다.
빠진조건에 맞게 수정하고 몇개의 데이터를 돌려보고 제출했다.
다른분들 코드 보니 y축마다 분할해서 푸신분이 대다수였는데 logic은 똑같았다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M, K;
int dp[2][101][3001][2]; // y,x,k,state
char map[101][101];
int get(int y, int x, int state) { // black : 1, white : 0
if (map[y][x] == 'W') {
if (state) return 1;
else return 0;
}
else {
if (state) return 0;
else return 1;
}
}
int main() {
int ans = 0x3f3f3f3f, tmp = 0x3f3f3f3f;
memset(dp, 0x3f, sizeof dp);
scanf("%d%d%d", &N, &M, &K);
for (int n = 0;n < N;n++) {
scanf("%s", &map[n]);
}
if (K == 0) { printf("%d\n", N*M); return 0; }
if (N == 1 && M == 1) { printf("%d\n", K == 0 ? 1 : 0); return 0; }
dp[0][0][1][0] = get(0, 0, 0);
dp[0][0][1][1] = get(0, 0, 1);
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
for (int k = 1;k <= K;k++) {
for (int f = 0;f < 2;f++) {
if (n == 0 && m == 0) {}
else {
dp[n % 2][m][k][f] = 0x3f3f3f3f;
if (m - 1 >= 0) {
dp[n % 2][m][k][f] =
min(dp[n % 2][m][k][f], dp[n % 2][m - 1][k][f] + get(n, m, f));
dp[n % 2][m][k][f] =
min(dp[n % 2][m][k][f], dp[n % 2][m - 1][k - 1][!f] + get(n, m, f));
}
else {
dp[n % 2][m][k][f] =
min(dp[n % 2][m][k][f], dp[!(n % 2)][M - 1][k - 1][!f] + get(n, m, f));
dp[n % 2][m][k][f] =
min(dp[n % 2][m][k][f], dp[!(n % 2)][M - 1][k - 1][f] + get(n, m, f));
}
}
if (dp[n % 2][m][k][f] != 0x3f3f3f3f) {
tmp = min(tmp, dp[n % 2][m][k][f] + M - 1 - m + (N - 1 - n)*M);
}
if (n == N - 1 && m == M - 1) ans = min(ans, dp[n % 2][m][k][f]);
}
}
}
}
if (ans != 0x3f3f3f3f) {
printf("%d\n", ans);
}
else {
printf("%d\n", tmp);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기