1633 최고의 팀 만들기

1633 최고의 팀 만들기 https://www.acmicpc.net/problem/1633

팀은 흑으로 플레이하는 15명, 백으로 플레이하는 15명으로 이루어진다.
플레이어는 흑 능력치, 백 능력치가 있으며 둘 중 하나를 선택할 수 있다.
팀 능력치는 플레이어의 능력치의 합이다.
가장 큰 능력치의 합을 구하는 문제다.

이 문제는 쉬웠음에도 불구하고 포스팅을 안할래야 안할 수가 없다.

세번의 실수를 했는데
 첫 번째로 문제를 잘못 파악해 흑과 백을 구분하지 않고 30명의 능력치의 최대합을 구했다.
 두 번째로 dp 함수의 base case를 $N+1$일때 반환해야하는데 $N$일 때 반환했다.
 세 번째로는 배열을 16으로 만들어야 15가 저장될 수 있는데 배열 크기를 15로 했다.

대회때 이런 실수를 하면 멘붕이 굉장히 심할것 같다...

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF (987654321) #define LINF (INF+INF) int    state[1111][2]; int N; int dp[1111][17][17][3]; int solve(int here, int cnt1, int cnt2, int flag) {     if (cnt1 == 15 && cnt2 == 15) return 0;     if (here == N + 1) return -INF;       int &ret = dp[here][cnt1][cnt2][flag];     if (ret != -LINF) return ret;     ret = -INF;     ret = max(ret, solve(here + 1, cnt1, cnt2, 2));     if (cnt1 + 1 <= 15)         ret = max(ret, solve(here + 1, cnt1 + 1, cnt2, 0) + state[here][0]);     if (cnt2 + 1 <= 15)         ret = max(ret, solve(here + 1, cnt1, cnt2 + 1, 1) + state[here][1]);     return ret; } int main() {     for (int n = 0;n < 1111;n++)for (int m = 0;m < 17;m++)for (int k = 0;k < 17;k++)for (int p = 0;p < 3;p++)         dp[n][m][k][p] = -LINF;     while (scanf("%d%d", &state[N][0], &state[N][1]) == 2) { N++; }     printf("%d\n", solve(0, 0, 0, 0));     return 0; } Colored by Color Scripter

cs