알고리즘/백준
백준 1633번 최고의 팀 만들기 C/C++ 풀이
Chavo Kim
2020. 8. 16. 13:36
https://www.acmicpc.net/problem/1633
1633번: 최고의 팀 만들기
문제 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 ��
www.acmicpc.net
전형적인 동적계획법 문제.
재귀함수와 메모이제이션을 이용해서 문제를 풀었다.
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
FILE* in = fopen("input.txt", "r");
int white[1001];
int black[1001];
int cache[1001][16][16];
int n;
int dp(int w, int b, int now) {
if (now == n)
return 0;
if (cache[now][w][b] != -1)
return cache[now][w][b];
int ret = 0;
if (w > 0)
ret = max(ret, dp(w - 1, b, now + 1) + white[now]);
if (b > 0)
ret = max(ret, dp(w, b - 1, now + 1) + black[now]);
ret = max(ret, dp(w, b, now + 1));
return cache[now][w][b] = ret;
}
int main() {
int tmp_w; int tmp_b;
memset(cache, -1, sizeof(cache));
while (fscanf(in, "%d %d", &tmp_w, &tmp_b) > 0)
{
white[n] = tmp_w; black[n] = tmp_b;
n++;
}
printf("%d", dp(15, 15, 0));
return 0;
}