# [Silver III] 카드 교환 [문제 링크](https://www.acmicpc.net/problem/31845) ## 문제 설명 <p>인하대학교 축제가 열리면, 인천 최대 규모의 카지노인 <strong>인하 카지노</strong>도 함께 문을 연다. 손님들의 더 많은 유입을 원했던 인하 카지노는 모두가 즐길 수 있는 새로운 카드 게임을 만들었다. 새로운 카드 게임의 진행 방식은 다음과 같다.</p> <p>딜러와 플레이어는 각각 $1$부터 $N$까지의 정수가 적힌 카드를 한 장씩 받는다. 딜러는 <strong>아무것도 적혀있지 않은 더미 카드 한 장</strong>을 추가로 받는다. 그리고 플레이어는 가진 점수가 $0$인 상태에서 게임을 시작하여 턴을 $M$회 수행한다. 각 턴은 아래와 같은 순서대로 진행된다.</p> <ol> <li>플레이어가 딜러의 패에서 원하는 카드를 하나 가져온다.</li> <li>플레이어의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우, 그 카드 쌍은 패에서 제거된다. 그리고 해당 카드 쌍에 적힌 값이 $i$라면 플레이어는 $A_i$점을 얻는다. 얻는 점수가 음수일 수 있으며, 플레이어의 점수도 음수가 될 수 있다.</li> <li>플레이어가 딜러에게 자신의 패에서 원하는 카드를 하나 준다.</li> <li>딜러의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우 그 카드 쌍은 패에서 제거된다. 이 경우 플레이어는 점수를 얻지 못한다.</li> </ol> <p>$M$번째 턴을 끝내거나 더미 카드를 제외한 모든 카드 쌍이 사라진 순간 게임이 종료된다. 즉, 턴이 수행되는 도중이라도 플레이어가 딜러에게 카드를 줄 수 없다면 게임이 즉시 종료된다.</p> <p>이 카드 게임에서 게임이 종료되었을 때 플레이어가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성해 보자.</p> ## 입력 <p>첫 번째 줄에 정수가 적힌 카드의 수 $N$과 게임의 최대 턴 수 $M$이 공백으로 구분되어 주어진다.</p> <p>두 번째 줄에 각 카드에 대해 플레이어의 패에 카드 쌍이 만들어질 때 얻을 수 있는 점수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다.</p> ## 출력 <p>플레이어가 얻을 수 있는 최대 점수를 출력한다.</p> ## 풀이 플레이어는 최대 min((n+1)/2, m)개의 카드를 가져갈 수 있습니다. 점수가 음수인 카드는 가져가지 않는 것이 좋으니, 큰 양수 카드만 최대 개수 만큼 가져가면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int a[1000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i=0;i<n;i++) cin >> a[i]; sort(a, a+n, greater<int>()); int sum=0; for(int i=0;i<min((n+1)/2, m);i++) { if(a[i]<0) break; sum += a[i]; } cout << sum; } ```