알고리즘 스터디

Google KickStart 2020 Round A

Plates

 

총 N개의 Plates 스텍이 있고, 각각 K 개의 plates가 있다.

P개의 Plates를 선택했을때 최댓값을 구하는 문제이다.

 

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The beauty values are between 1 and 100, inclusive.

 

C++를 사용한 제 풀이입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

int n, k, p;

void solve() {
	cin >> n >> k >> p;
	vector<vector<int>> a(n, vector<int>(k));
	vector<int> dp(p + 1, 0);

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < k; ++j) {
			cin >> a[i][j];
		}

		partial_sum(a[i].begin(), a[i].end(), a[i].begin());
		vector<int> tmp = dp;

		for (int l = 0; l < k; ++l) {
			for (int m = l + 1; m <= p; ++m) {
				tmp[m] = max(tmp[m], dp[m - (l + 1)] + a[i][l]);
			}
		}

		dp = tmp;
	}

	cout << dp[p] << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	for (int i = 1; i <= t; ++i) {
		cout << "Case #" << i << ": ";
		solve();
	}
}

알고리즘 시간에 배웠던 동적 프로그래밍 0/1 냅색 알고리즘을 떠올려서 어느정도 검색하고 디버그 찍어보면서 풀었다..

아직 너무 어렵다.