[백준 / BOJ] 11062 카드게임

문제

출처 : www.acmicpc.net/problem/11062

11062번: 카드 게임

근우와 명우는 카드게임을 하고있다. 

근우부터 시작하여 번갈아가면서 카드를 선택하는데, 이때 서로가 최선의 전략으로 임할때 근우가 얻는 최대점수를 구하는문제다.

(단, 남아있는 카드중 가장 오른쪽과 가장끝만 선택할수있다.)

 

풀이

어려웠던 문제였다.

서로가 항상 최선의 전략으로 임한다고 하는데, 어떤 걸 선택해야 최선의 상황이 되는지 모르기 때문에 모든경우를 다 봐줘야한다.

 

플레이어(근우와 명우)는 매 턴마다 두가지 선택지(왼쪽 끝 카드와 오른쪽 끝 카드)중 하나를 고를수있다. 이는 항상 두가지 갈래로 나뉘는것 을 뜻하고, 플레이어가 선택하는 모양을 이진트리로 나타낼수있다. 

 

다음 그림과 같은 구조를 생각할수있다. 

현재 남아있는 카드가 (1, 2, 3) 일때, 왼쪽 끝 1 과 오른쪽끝 3을 선택할수있다. 만약 1을 선택한다면 남아있는 카드는 (2,3) 이 되고 3을 선택하면 (1, 2)가 될것이다.

 

 

이진트리 탐색을 바텀업으로 구현해서 근우의 차례일경우 최댓값을 올려주고, 만약 명우의 차례일경우 최솟값을 올려줬다.(근우의 점수가 작아질수록 명우의점수는 커지므로)

 

처음에는 선택이 1000번이고 카드의 최대 개수가 1000이므로 

int dp[1005][1005][1005] 와 같이 선언해서 풀려고했었다. 전역변수 크기를 줄일 아이디어가 도저히 떠오르지않아서, 다른분들 코드를 참조했는데, 사실 선택횟수는 중요하지않았다. (결국 처음 입력받은 카드에서 줄어든 수 만큼 선택한것 이므로...) 

배열을 dp[1005][1005]로 바꿔주고, 만약 한번 탐색한곳이라면, 더이상 들어가지않고 리턴해주면서 시간을 줄였다.

배열을 이렇게 설정하면,

dp[왼쪽끝][오른쪽끝] = 최댓값 (카드가 왼쪽에서 오른쪽까지 남은 상황에서의 최댓값) 처럼 나타낼수있다. 

그럼 트리탐색을 끝내고, dp[1][N]에 저장되어있는값이 서로가 최선의 선택으로 임했을때 근우가 얻을 점수다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11062%20%EC%B9%B4%EB%93%9C%EA%B2%8C%EC%9E%84/main.cpp

devxb/JJUNalgo