KOI 2015 기출문제

문제

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
(1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

얻을 수 있는 최종 점수의 최댓값을 출력한다.

자세한 예시와 입출력 양식은 문제 링크 참조

접근 과정

우선은 카드를 한장한장 열어보는 방법을 고민해보았다. 카드 한 장, 한 장 뽑는 상황을 재귀함수를 통해 구현할 수 있었으나 생각보다 연산하는 양이 많았다.
2개의 더미에서 카드를 뽑는 순서가 다르더라도 중복되는 경우의 수가 많음을 확인할 수 있었다. 따라서 특정한 상태에서 얻을 수 있는 점수의 최댓값을 따로 캐시 배열에 저장해두고 필요할 때 계산하지 않고 캐시에서 가져오는 방식으로 구현하였다.
게임의 진행 과정과 같이 카드의 양을 N에서 1까지 줄이는 방식으로 구현하였으나 채점시 100%를 채울 수 없었다. 배열범위 밖을 인덱싱하며 생긴 문제일듯 싶어 최대한 보완해봤으나 50% 부근을 넘어서면 바로 실패하더라. 결국 완전히 해결할 수 없었고 1에서 N 까지 늘이는 방식으로 함수를 고치고 나서야 통과할 수 있었다. 실패한 함수도 아래 소스 코드에 포함시켜두었다.(getMaxScore_Fail)

소스 코드

#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;

int N;
int cache[2010][2010];
int lDummy[2010], rDummy[2010];

int getMaxScore(int l, int r) {
    if (l == N || r == N) {
        return 0;
    }

    int& ret = cache[l][r];

    if (ret != -1) {
        return ret;
    }

    ret = max(getMaxScore(l + 1, r), getMaxScore(l + 1, r + 1));

    if (lDummy[l] > rDummy[r]) {
        ret = max(ret, getMaxScore(l, r + 1) + rDummy[r]);
    }

    return ret;
}

int main(void) {
    memset(cache, -1, sizeof(cache));
     
    cin >> N;

    for (int i = 0; i < N; ++i) {
        cin >> lDummy[i];
    }

    for (int i = 0; i < N; ++i) {
        cin >> rDummy[i];
    }

    cout << getMaxScore(0, 0);
    //cout << getMaxScore_Fail(N-1, N-1);

    return 0;
}

int getMaxScore_Fail(int l, int r) {
    if (l < 0 || r < 0) {
        return 0;
    }

    int& ret = cache[l][r];

    if (ret != -1) {
        return ret;
    }

    // 왼쪽 카드만 버린 경우 & 왼쪽 오른쪽 둘 다 버린 경우
    ret = max(getMaxScore(l - 1, r), getMaxScore(l - 1, r - 1));

    // 오른쪽 카드가 작을 때 오른쪽만 버린 경우(득점)
    if (lDummy[l] > rDummy[r]) {
        ret = max(ret, getMaxScore(l, r - 1) + rDummy[r]);
    }

    assert(ret != -1);

    return ret;
}