[Code SASA] 숫자 카드 게임

[Code SASA] 숫자 카드 게임

2020. 5. 15. 00:27ㆍPS/Problem Solving

SASA OJ

첫 번째 줄에 카드의 개수(1<=n<=100000)가 입력되고, 두 번째 줄에는 그 수만큼 카드에 적힌 숫자(0<=k<=1000)가 띄어쓰기로 구분되어 입력된다. 이때, 카드의 숫자가 1000장 이상일 때에는 카드의 개수

code.sasa.hs.kr

DP[s,e]를 s~e번째 카드를 보고 있을 때 얻을 수 있는 최대의 점수라 하자.

관계식은 간단하게 세울 수 있다.

DP(s,e) = max(arr[s]+sum[e]-sum[s]-DP(s+1,e),arr[e]+sum[e-1]-sum[s-1]-DP(s,e-1));

s,e는 1~n이고 n은 1e5까지 가능하기 떄문에 DP는 일반적인 방법으로 채울 수 없다.

최적화가 필요하다!

이 문제를 푸신 선배 "최성준" 님께 여쭈어봐서 유사한 문제를 알아냈다.

11062번: 카드 게임

문제 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 �

www.acmicpc.net

이 문제는 N의 제한이 1000이기 때문에 기존에 생각한 N^2풀이가 가능하다.

기존 풀이를 제출했을 때 92 ms 가량이 나왔는데, 4ms 로 푼 분이 있어 그분의 코드를 보고 공부했다.

핵심 아이디어는 동적 계획법 -> 그리디 변환이다.

Pentagon