백준 31845 - 카드 교환(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31845

 

딜러와 카드를 주고 받을 때 얻을 수 있는 최고 점수를 구하는 문제입니다.

 

플레이어는 원하는 카드를 주고 받을 수 있기 때문에 항상 최고 점수 카드를 받고 최저 점수 카드를 주는 것이 최고입니다.

따라서 먼저 정렬을 통해 카드의 점수를 정렬해줍니다.

 

순서대로 최고 점수 카드를 더하고, 최저 점수 카드를 없애면서, 각 턴들의 최고 점수들을 저장합니다.

 

마지막에 저장된 점수들 중에서 가장 큰 점수를 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
int card[1001];
int dp[1001][2];

void solve() {
	sort(card, card + N);
	int point = 0;
	for (int i = 1; i <= M; i++) {
		dp[i][0] = -987654321;
		dp[i][1] = -987654321;
	}
	int fin = N - 1, st = 0;
	for (int i = 1; i <= M; i++) {
		if (st > fin) break;
		point += card[fin];
		dp[i][0] = max(dp[i][0], point);
		dp[i][1] = max(dp[i - 1][1] + card[fin], dp[i - 1][0]);
		st++;
		fin--;
	}
	int ans = -987654321;
	for (int i = 1; i <= M; i++) {
		ans = max(ans, dp[i][0]);
		ans = max(ans, dp[i][1]);
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> card[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.