[일반] 이번 C같은거 어떻게 풀어야 하나요??

[익명(61.98)]

https://codeforces.com/problemset/problem/1738/C

결국에 어떻게 어떻게 풀기는했는데..

이런 유형이 너무 어렵네요 ㅠㅠ

고민고민끝에 짝수 홀수 일 때 나눠서 다 생각해보자 하고 케이스 분류 했거든요..?

초괴수분들은 이런문제 보면 어떻게 접근하시는지 궁금합니다..!!

[익명(61.253)]

그건 O(1)로 풀고 싶을때 하는거고 그냥 N^2 DP 박으면 됨

[익명(61.98)]

n^2 dp 는 어떤식으로 생각하면 되나요??

[익명(49.168)]

일단 A / B가 할 수 있는 행동 홀수 먹기 아니면 짝수 먹기임 A가 어떠한 행동을 했을 때 B가 홀수를 먹는 경우 짝수를 먹는 경우 둘 다 A를 이기게 한다면 A의 승리고 그것이 아닌 경우에는 A의 패배임 초기 홀수와 짝수의 개수를 상태로 정의해서 dp 배열을 채워나가면 됨

[익명(61.253)]

일단 문제 상황이 (홀수의 개수, 짝수의 개수) 순서쌍으로 정의됨을 알아야 하고 A나 B가 숫자를 가져가면, 위의 순서쌍이 조금씩 작아지니까 "부분 문제"가 된다는 것을 알아야 함

[익명(61.98)]

와 진짜 두 분다 자세한 풀이 감동입니다!! 이따가 읽어보면서 공부해봐야겠네요 ㅎㅎ