[BOJ/Gold 3] 백준 26607 시로코와 은행털기(C++)

문제 링크

https://www.acmicpc.net/problem/26607

 

문제

블루아카이브에 있는 아비도스 고등학교 학생, 스나오오카미 시로코는 은행 터는 것을 자주 시뮬레이션한다.

 

 

게임의 마스코트, 스나오오카미 시로코이다.

어느 날, 정말로 은행을 털어보고 싶다는 생각이 든 시로코는 은행을 털 준비를 하기 시작했다. 우선, 은행 터는 것을 함께 할 팀을 만들 것인데, 경쟁을 뚫고 마지막까지 살아남은 n명 중에서 최종적으로 k명을 팀원으로 선발할 계획이다. 지원자들은 각각 힘과 스피드 수치 a, b가 주어지는데, 쟁쟁한 경쟁을 뚫고 살아남은 자들답게 a + b가 모두 동일하다.

 i번째 팀원으로 선발한 사람의 능력치가 각각 ai, bi라 할 때, 그 팀의 종합 능력치는 (∑i=1kai)×(∑i=1kbi)이다. 팀의 능력치를 최대화하게 지원자들을 선발하려 할 때 그때 그 팀의 능력치를 출력하라.

 

입력

첫 번째 줄에 사람의 수 n와 뽑을 인원 k, 그리고 힘과 스피드 수치의 합 x가 공백으로 구분되어 주어진다.

그 다음줄부터 n개의 줄에는 각 사람들이 지닌 힘과 스피드 능력치 a b가 주어진다.

 

출력

팀의 능력치를 최대화하게 인원을 선발할 때, 그 팀의 능력치를 출력하라.

 

제한

•  1 ≤ n ≤ 80
•  1 ≤ k ≤ n
•  1 ≤ x ≤ 200
•  0 ≤ a, b

 

예제 입력 1

4 2 4
0 4
1 3
3 1
2 2

예제 출력 1

16

 

 

2번째와 3번째 사람으로 팀을 구성하면 팀의 능력치가 4 × 4 = 16이 되고, 이것이 최대이다.

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

DP[N][K][X * K]라는 3차원 배열을 선언한다. 이는 N번째 사람까지 탐색했을 때, K명을 선택했을 때의 힘 수치의 총합이 X * K일 때의 스피드 수치의 총합의 최대치를 의미한다.

1번째 사람부터 선발할지 선발하지 않을지를 결정하는데, 이 때 선발하는 조건은 해당 인원을 선발하면서 증가하는 힘 능력치가 X * K를 넘지 않아야 한다는 것이다.

마지막으로, K명을 선택했을 때의 힘 수치의 총합이 X * K일 때의 스피드 수치의 총합을 구한 경우에 한정해서 A의 총합 * B의 총합의 최댓값을 구한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX_N 81
#define MAX_X 201
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int N, K, X;
int A[MAX_N], B[MAX_N];
int DP[MAX_N][MAX_N][MAX_N * MAX_X];
int Answer;

void init() {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            for (int k = 0; k < (MAX_N * MAX_X); k++) {
                DP[i][j][k] = -1;
            }
        }
    }
    DP[0][0][0] = 0;
    DP[1][0][0] = 0;
}

void input() {
    cin >> N >> K >> X;
    for (int i = 1; i <= N; i++) {
        cin >> A[i] >> B[i];
    }
}

void settings() {
    for (int i = 1; i <= N; i++) {
        for (int j = i; j >= 1; j--) {
            for (int k = 0; k <= (K * X); k++) {
                if (DP[i - 1][j - 1][k] == -1) continue;
                DP[i][j - 1][k] = max(DP[i][j - 1][k], DP[i - 1][j - 1][k]);
                if (k + A[i] <= (K * X)) {
                    DP[i][j][k + A[i]] = max(DP[i][j][k + A[i]], DP[i - 1][j - 1][k] + B[i]);
                }
            }
        }
    }
    for (int i = 0; i <= (K * X); i++) {
        if (DP[N][K][i] > -1) {
            int B = (K * X) - i;
            Answer = max(Answer, i * B);
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}