[JAVA][백준 11062][게임 이론][DP] 카드 게임 - 컴도리돌이

반응형

11062번: 카드 게임

---

근우가 왼쪽/오른쪽을 선택했을 때 명우가 선택할 카드의 합이 최소가 되어야 한다.
맨 왼쪽/오른쪽 카드의 수만 비교해서는 최선의 선택이 되지 않기 때문에
다이나믹 프로그래밍으로 접근해야 한다.

여기서 주의할 점은 근우와 명우의 차례에 따라서 구하는 식이 다르기 때문에 2차원 배열을 사용해야 한다.
근우와 명우가 카드를 선택하다가 남은 카드의 상태를 점화식을 세우고,
dp [i][j] = i~j의 카드가 있을 때 근우가 선택할 수 있는 최대 합을 만들어야 한다.
n이 홀수일 때는 근우, 짝수일 때는 명우 차례로 설정하였다.
근우 차례일 경우 i~j 카드가 있을 때 선택할 카드와 다음에 선택할 카드의 합이 최대가 되도록 선택해야 하고,
명우 차례일 때는 명우가 선택 후 남은 카드들로 근우가 선택할 카드의 합이 최소가 되도록 선택해야 한다.
size가 0일 때 근우의 차례가 아니면, 카드 선택을 하지 않기 때문에 0으로 할당한다.

---