11062. 카드 게임

 

재미있는 카드놀이~

11062번: 카드 게임

---

카드 N개가 일렬로 놓여 있다. 근우와 명우가 번갈아가며 카드를 집으려 한다. 양 끝에 있는 카드만 집을 수 있으며, 집은 카드에 적힌 수만큼 자신의 점수가 증가한다. 근우와 명우 모두 "최선의 전략"으로 게임에 임한다. 이때 근우가 얻을 수 있는 점수는 몇 점일까?

 

최선의 전략이라는 말에 대해 이해해 보자. 근우와 명우의 목적은 지금 당장 큰 점수를 얻는 것이 아니다. 당장은 작은 점수를 얻더라도 추진력을 얻어서 마지막에 가장 큰 점수를 얻는 것이 이 게임의 목적이다.

 

그렇다. 이 문제는 그리디가 아니다. ㅋㅋ

무조건 양 끝에서 가장 큰 카드를 집는 것은 정답에는 가까울 수 있으나, 정답은 아니다. 이것을 생각했다면 반은 푼 것이다. 시작이 반이니까

---

 

당장의 이득만을 좇으면 안 된다는 사실을 깨달았다. "큰 그림"을 그리기 위해서는 이 카드를 집었을 때 내가 몇 점을 얻을 수 있을지를 알아야 한다. 그렇다면 이전 결과를 미리 알아야 하지 않겠는가?

 

여기까지 읽었다면 본능적으로 DP를 생각해야 할 것이다. 작은 문제로부터 시작하여 전체 정답을 만들면 된다. 이런 것을 bottom-up이라고 한다. 자, 이제 코드를 짜 보자.

 

 

그럼에도 불구하고 잘 모르겠다면(ㅠㅠ) 다음을 읽어 보자.

i~j번째 구간의 정답을 구해 보자.

 

카드를 먼저 집는 사람은(근우가 아님에 유의) i번 또는 j번 카드를 집을 수 있다.

[CASE 1] i번 카드를 집을 때의 점수는 card[i] + ((i+1)~j 구간에서 나중에 집는 사람이 얻는 점수)이다.

[CASE 2] j번 카드를 집을 때의 점수는 card[j] + (i~(j-1) 구간에서 나중에 집는 사람이 얻는 점수)이다.

 

따라서 먼저 집는 사람은 최대 max(CASE 1, CASE 2)점을 얻을 수 있다. 

 

나중에 집는 사람이 얻는 이득은 각각

[CASE 1] (((i+1)~j 구간에서 먼저 집는 사람이 얻는 점수)

[CASE 2] (i~(j-1) 구간에서 먼저 집는 사람이 얻는 점수)

이다.

 

dp 배열을 만들어서 차례차례 저장하면 된다. 이때 기저 사례로

dp[i][i] = card[i]

dp[i][i + 1] = max(card[i], card[i+1])

를 미리 저장해놓고 시작하자.

---