BOJ 28039번 - 카드 게임 2

28039번: 카드 게임 2

ICPC 인터넷 예선 2015 B번 문제에서 N 제한을 키운 문제이다.

기존 문제의 경우 O(N^2) dp 풀이가 가능하지만 이 문제의 최대 N은 1e6이다.

 

먼저 나는 이 문제를 풀지 못하였고 다른 사람의 코드를 보고 풀었음을 밝힌다.

엄밀한 증명 없이 대강 감만 잡은 상태에서 작성하는 글이기 때문에 잘못된 내용이 있을 수 있다.

잘못된 내용이 있다면 지적 부탁드립니다.

 

다음과 같은 배열 A를 정의하자.

A[i] = i번 카드에 적힌 수

배열 A의 값을 그래프로 그렸을 때 아래로 볼록한 모양이라고 가정해보자.

이 경우에는 two pointer로 그리디하게 최적해를 구할 수 있음을 쉽게 증명할 수 있다.

 

그렇다면 임의의 배열 A를 아래로 볼록한 모양으로 만들 수 있을까?

먼저 배열 A를 다음과 같이 재정의하자.

A[i] = i번 카드를 가져갔을 때 상대적인 이득

현재로서는 기존 정의와 별다를 바 없어 보인다.

 

편의를 위하여 배열 A의 모든 원소가 서로 다르다고 가정하자.

그리고 배열 A에서 임의의 인접한 세 원소 a, b, c를 선택하자.

배열 A가 아래로 볼록한 모양이려면 모든 a, b, c에 대하여 (b < max(a, c))를 만족하여야 한다.

따라서 이를 만족하지 않는, 즉 (b > max(a, c))를 만족하는 a, b, c를 모두 제거할 수 있다면 배열 A는 아래로 볼록해질 것이다.

 

이제 이를 제거하는 방법을 알아보자.

나와 상대방 모두 a와 c보다는 더 높은 점수를 가진 b를 원할 것이다.

내가 a 또는 c를 가져간다면 상대방은 b를 가져가는 것이 최선의 전략이다.

따라서 특별한 목적이 없다면 a와 c 모두 건드릴 이유가 없다.

 

하지만 일시적으로 손해를 보더라도 a(또는 c)를 가져가는 것이 이득이 될 수도 있다.

내가 a를 가져가면 상대방은 b를 가져가고 나는 c를 가져가는 것이 최선의 전략이다.

내가 c를 가져가지 않고서는 상대방에게 b를 순순히 넘겨줄 이유가 없다.

 

이때의 상대적인 이득을 계산하면 (a - b + c)가 된다.

따라서 (b > max(a, c))를 만족하는 인접한 세 원소 a, b, c를 (a - b + c)로 대체할 수 있다.

이 작업을 가능할 때까지 반복하면 배열 A를 아래로 볼록하게 만들 수 있으며 O(N)이 소요된다.

이제 위에서와 마찬가지로 two pointer로 그리디하게 최적해를 구할 수 있다.

이때 최종적으로 얻는 값은 "상대적인 이득"임에 주의해야 한다.

 

더 나은 설명이 가능하다면 댓글 부탁드립니다.

 

끝