백준 31845

문제

인하대학교 축제가 열리면, 인천 최대 규모의 카지노인 인하 카지노도 함께 문을 연다. 손님들의 더 많은 유입을 원했던 인하 카지노는 모두가 즐길 수 있는 새로운 카드 게임을 만들었다. 새로운 카드 게임의 진행 방식은 다음과 같다.

딜러와 플레이어는 각각 1부터 𝑁까지의 정수가 적힌 카드를 한 장씩 받는다. 딜러는 아무것도 적혀있지 않은 더미 카드 한 장을 추가로 받는다. 그리고 플레이어는 가진 점수가 0인 상태에서 게임을 시작하여 턴을 𝑀회 수행한다. 각 턴은 아래와 같은 순서대로 진행된다.

1. 플레이어가 딜러의 패에서 원하는 카드를 하나 가져온다.
2. 플레이어의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우, 그 카드 쌍은 패에서 제거된다. 그리고 해당 카드 쌍에 적힌 값이 𝑖라면 플레이어는 𝐴𝑖점을 얻는다. 얻는 점수가 음수일 수 있으며, 플레이어의 점수도 음수가 될 수 있다.
3. 플레이어가 딜러에게 자신의 패에서 원하는 카드를 하나 준다.
4. 딜러의 패에서 같은 값을 가진 카드 쌍이 만들어진 경우 그 카드 쌍은 패에서 제거된다. 이 경우 플레이어는 점수를 얻지 못한다.

 𝑀번째 턴을 끝내거나 더미 카드를 제외한 모든 카드 쌍이 사라진 순간 게임이 종료된다. 즉, 턴이 수행되는 도중이라도 플레이어가 딜러에게 카드를 줄 수 없다면 게임이 즉시 종료된다.

이 카드 게임에서 게임이 종료되었을 때 플레이어가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성해 보자.

 

풀이

경우의 수 생각하다 두번틀렸다..

모든 경우에서 더미카드를 사용할 수 있는게 아니다. 플레이어가 높은 점수의 카드를 가져가면, 무조건 가장 낮은 점수의 카드를 하나 줘야한다. 그리고 가장 높은 점수가 음수라면 스킵하면 된다.

입력받은 카드를 한번씩만 돌면 된다. 그러므로 정렬에 소요되는 시간복잡도가 이 문제의 시간복잡도이다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, arr[1001], ans;
int main() {
    cin>>N>>M;
    for(int i=0; i<N; i++) cin>>arr[i];
    sort(arr, arr+N);
    int banker = 0;
    for(int i=N-1; i>=banker; i--) {
        if(arr[i] > 0) {
            ans += arr[i];
            banker += 1;
        }
        if(i == N-M) break;
    }
    cout<<ans;
        
}