10835 카드게임

https://www.acmicpc.net/problem/10835

10835번: 카드게임

 

존나 어렵다

골드 DP 문제중에서 제일 어려웠던거 같다 

일단 이게 랜디로 돌려서 나온거라 DP인줄도 몰랐고

태그 까도 DP테이블 짜는게 정말 어렵다

DP테이블 짜도, 또 하나의 조건을 조심해야한다

DP테이블 순회할 때, 해당 지점을 방문 했는지 유무가 필요하다

그래서 다른 풀이들을 보면 -1로 초기화하거나 아니면 아싸리 재귀를 돌리거나 한다

나는 그냥 불린배열 하나 새로 만들었다

이중 포문 두번 돌리는건 좀 아니다

 

DP[i][j] : 왼쪽 더미의 i번째 카드, 오른쪽 더미의 j번째 카드를 의미

DP[i+1][j] : 왼쪽 더미의 i번재 카드를 버림

DP[i][j+1] : 오른쪽 더미의 j번째 카드를 버림 ( 이건 조건 충족이 필요 )

DP[i+1][j+1] : 둘 다 버림

 

보다시피 DP[i+1][j], DP[i+1][j+1] 는 조건이 필요없어서 막 하면되는데

DP[i][j+1] 는 L[i]랑 R[j] 의 값 비교가 필요하다

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0027.java