문제
https://www.acmicpc.net/problem/2629
제공받은 추를 이용해 특정 구슬의 무게를 확인할수 있는지 여부를 체크하는 문제입니다.
추의 무게는 모두 알고있기 때문에 구슬의 무게를 미지수로 두고 풀수 있는 1차방정식 느낌..?
하지만 추의 개수가 30개이고, 같은 무게의 추가 여러개 있을 수 있으며, 추의 무게는 상한선이 500g입니다. 구해야 하는 구슬의 무게는 40000g인데, 직접 하나하나 더하고 빼는걸 모두 구하다 보면 3^30의 경우의 수가 나오게 됩니다.
다행히 추의 무게는 고정값이기 때문에, 어떤 구슬이 오더라도 같은 무게를 빼고 더할 수 있어서 기존에 나왔던 경우의 수를 재활용하면 시간을 효과적으로 단축시킬 수 있습니다. -> dp를 사용해야 합니다!
1차 시도
#include <stdio.h>
#include <string.h>
int n, m, dp[40001][30], g[30];
int f(int v, int c) {
if (!v) return 1;
if (v < 0) return 0;
if (dp[v][c] >= 0) return dp[v][c];
dp[v][c] = 0;
for (int i = c; i < n; i++) {
if (f(v + g[i], c + 1)) dp[v][c] = 1;
if (f(v - g[i], c + 1)) dp[v][c] = 1;
}
return dp[v][c];
}
int main() {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++) scanf("%d", &g[i]);
scanf("%d", &m);
for (int i = 0, a; i < m; i++) {
scanf("%d", &a);
printf("%c ", f(a, 0) ? 'Y' : 'N');
}
}3%에서 틀렸습니다를 받았습니다. 무게추를 모두 사용해야 하는줄 알고 for문을 돌려서 하나하나 탐색했는데 문제를 꼼꼼하게 읽고 나니 아니더라고요.. 백트래킹 + 캐싱 느낌으로 무게 빼기, 추 안쓰기, 무게 더하기 3가지를 재귀로 돌리면서 방문했던곳만 재사용해주었습니다.
또한 구슬의 무게가 4만이다 보니까 추의 무게를 더하거나 빼는 과정에서 배열 크기를 초과할 수 있기 때문에, 초기값을 4만으로 두고 8만으로 배열 크기를 잡아서 배열을 넘어가지 않도록 조절해주었습니다.
2차 시도
#include <stdio.h>
#include <string.h>
int n, m, dp[80001][30], g[30];
int f(int v, int c) {
if (!c) return v == 40000;
if (dp[v][c] >= 0) return dp[v][c];
return dp[v][c] = f(v + g[c], c - 1) | f(v - g[c], c - 1) | f(v, c - 1);
}
int main() {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++) scanf("%d", &g[i]);
scanf("%d", &m);
for (int i = 0, a; i < m; i++) {
scanf("%d", &a);
printf("%c ", f(a + 40000, n) ? 'Y' : 'N');
}
}
11%에서 틀렸습니다. 상당히 바보같은 실수를 해버렸는데요.. 4만이 초기값인데 4만을 더해버리면 8만 스타트인데 당연히 out of bounds를 맞을수밖에 없었습니다.. 추의 무게의 합이 500g 30개니까 15000g임을 고려해 15000을 초기값으로 해주었습니다. 이렇게 되면 상한선 55000에 하한선 0으로 충분히 가능해집니다. 초기값이 15000이기 때문에 [70001][30]으로 배열크기를 잡아주면 딱 맞습니다.
3차 시도
#include <stdio.h>
#include <string.h>
int n, m, dp[80001][30], g[30];
int f(int v, int c) {
if (!c) return v == 15000;
if (dp[v][c] >= 0) return dp[v][c];
return dp[v][c] = f(v + g[c], c - 1) | f(v - g[c], c - 1) | f(v, c - 1);
}
int main() {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++) scanf("%d", &g[i]);
scanf("%d", &m);
for (int i = 0, a; i < m; i++) {
scanf("%d", &a);
printf("%c ", f(a + 15000, n) ? 'Y' : 'N');
}
}메모리 10492kb에 4ms의 시간으로 통과한 코드입니다. 사실 knapsack problem으로 풀 수 있는 문제였지만 암튼 풀었으니 ok입니다. 개인적으로 처음 생각한 방법으로 밀어붙이는걸 좋아하는 편이라..ㅎㅎ;
메모리를 8만 x 30에서 7만 x 30으로 줄이고 나서 약 1100kb의 메모리를 아꼈습니다. 다른 분들은 1112kb로 푸시던데 대단할 따름..
음수 인덱스 접근때문에 공간을 일부러 크게 잡았는데 map을 쓴다면 불필요한 부분은 조금 줄일수 있지 않을까 싶습니다. 아니면 진짜 배낭 + 상향식으로 메모리 빡 줄여도 해볼만할것같고.. 근데 그런거 바로 생각할 줄 아는 사람은 진짜 대단한것같네요..
