게임 이론 (31) 썸네일형 리스트형 [Python] 32871번 돌 게임 nm https://www.acmicpc.net/problem/32871 24/12/03 좋은 아이디어를 가진 게임 이론 문제다. 문제 접근 방식: 문제 접근 방식의 핵심은, 행과 열의 쪼개진 부분을 붙여서 새로운 블록으로 생각해도 상관 없다는 것이다. 예를 들어, 다음과 같다.$3 \times 4$크기의 판에서 $2$번 열을 선택해서 없앴다면,이렇게 그냥 새로운 $3 \times 3$짜리 크기의 판으로 생각해도 된다는 점이다. 편의 성을 위해, $N 그러면, 일단 $N = 1$인 경우 선공이 항상 이김은 당연하다. $N = 2$이고 $M = 2$라면, 선공은 무슨 짓을 해도 $N = 1$인 경우로 되돌아가므로 선공이 진다. $N = 2$이고 $M = 3$이라면, 선공은 $N=2, M=2$인 상태를 상대.. [Python] 29154번 작곡가 A의 시창 평가 https://www.acmicpc.net/problem/29154 24/05/16 이전에 해결했었던 스그 문제인데, 꾸역꾸역 kmp랑 엮어서 만들었다는 느낌을 너무 강하게 받은 문제이다. 문제 접근 방식: 일단 선/후공 승패 여부 판단하고, 색칠된 부분이 여러 개의 모습으로 분리되며, 색칠된 부분을 그냥 님게임으로 간주할 수 있다는 사실은 스프라그 그런디 정리를 많이 풀어본 사람이라면 쉽게 파악할 수 있을 것이다. 문제는 그러면 색칠된 부분을 어떻게 빠르게 구할건데?가 핵심이 된다. 보면 멜로디 $L$과 멜로디 $L$의 접미사들을 "모두" 기존 문자열 $S$에서 찾아야 한다.(빠르게) 그러면 당연히 생각나는건? kmp다. kmp의 동작 원리를 생각하면 접두사와 접미사가 일치하는 부분을 통해 "당겨옴.. [Python] 32645번 동까뚱뽭 게임 https://www.acmicpc.net/problem/32645 24/11/11 간단한 게임이론 + 트리 DP문제이다. 문제 접근 방식: DP상태 식을 다음과 같이 정의해보자. DP[i] = $i$번째 노드에서 게임을 진행할 때 누가 이기는 지에 대한 여부 DP[i] = 0이라면 후공이 이긴다고 하고, 1이라면 선공이 이긴다고 하자. 뭐, 게임이론 많이 한 사람들이라면 스프라그-그런디로 생각해서 mex때릴 수도 있는데, 사실 게임이 하나 뿐이라서 선후공 승패 여부만 따지면 되기 때문에 간단한 게임 DP로도 풀린다. $i$번째 노드에서 밑으로 갈 수 있는 노드를 below라고 한다면, DP[below]가 모두 1이라면, 즉, 선공이 이기는 노드라면 현재 노드는 후공이 이기는 노드(즉, 선공이 지는 .. [Python] 32299번 게임을 만들어요 https://www.acmicpc.net/problem/32299 24/11/10 전형적인 게임이론 문제다. 문제 접근 방식: $N=3$인 경우를 제외하면 항상 후공이 이긴다. 그 이유는 게임 판을 도넛 모양으로 분리하면, 한 도넛에서 다른 도넛으로 움직일 때마다 선공과 후공의 유리한 정도가 달라지는데, 다른 도넛으로 움직일 때 후공이 유리하다면 후공은 그냥 그 방향으로 움직이면 되고, 다른 도넛으로 움직일 때 선공이 유리하다면, 후공이 현재 도넛에서 빙빙 돌면서 선공이 다른 도넛으로 넘어가도록 만들 수 있기 때문이다. 게임이론에서 자주 나오는 테크닉인데, 핵심은 후공이 항상 선공이 불리하도록 게임판을 "조정"할 수 있다는 것이 핵심이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다... [Python] 32232번 엉엉이의 저주 탈출 https://www.acmicpc.net/problem/32232 24/09/13 맷코컵 검수 당시 검수했던 문제 중 하나이다. 문제 해석을 잘 한다면 막혔던 부분이 뚫리면서 쉽게 문제를 해결할 수 있을 것이다. 문제 접근 방식: 먼저 많은 관찰을 통해 다음과 같은 두 가지 사실을 발견해야 한다.(물론 오일러 지표를 통해 직접 유도하고 증명해도 충분하다.) 1. 엉엉이와 현철이가 지금까지 뽑은 서로 다른 점의 개수가 짝수 개라면 면이 홀수 개로 분할되고, 홀수 개라면 면이 짝수 개로 분할 된다. 2. 현철이는 자신이 이전에 뽑았던 점을 다시 뽑음으로써 홀짝성을 조정할 수 있다. 내가 이 문제에서 가장 어렵다고 느꼈던 점은 현철이와 엉엉이 모두 동일한 "확률"로 정수를 뽑는 상황, 즉, 게임에 랜덤이.. [Python] 32233번 토러스 게임 조작하기 https://www.acmicpc.net/problem/32233 24/09/12 오일러 지표 + 스프라그 그런디 + 가우스 소거법의 세 가지 태그가 잘 맞물리는 좋은 문제이다. 맷코컵 검수했을 때의 기억을 되살려서 꼼꼼하게 해설을 적어보고자 한다. 문제 접근 방식: 이 문제를 해결하기 위해서는 다음과 같은 세가지 지식을 알고 있어야 한다. 1. 오일러 지표에 대한 지식 2. 스프라그-그런디 정리에 대한 지식 3. 가우스 소거법, 특히, 2진법 위에서의 가우스 소거법에 대한 지식. 먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다. 이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다.. [Python] 32213번 래빗 홀 https://www.acmicpc.net/problem/32213 24/09/05 간단한 스프라그-그런디 문제이다. 관찰의 아이디어가 좋아서 작성해본다. 문제 접근 방식: 두 사람이 할 수 있는 행동은 동일하다. 둘 중 하나이다. 1번 행동은 일반적인 님 게임이다. 근데 걸리는 점은 2번 행동이다. 2번 행동이 1번 행동에 영향을 줄 수 있을까, 곰곰히 생각해보면 아니다. 얼핏 생각하면 영향을 줄 수 있을 것 같지만 2번 행동이 전체 XOR의 합에 영향을 끼치지 못하므로 1번 행동과 독립이다. 결국 2번 행동은 홀짝성에 관한 게임을 개별적으로 하는 것과 동치이다. 즉, 님 게임과 홀짝 게임을 동시에 하고 있는 것과 동치이다. 처음에는 이러한 사실 때문에 님게임 XOR값과 홀짝성 모두 만족하면 후공 .. [Python] 12070번 gNumbers (Small) / 12071번 gNumbers (Large) https://www.acmicpc.net/problem/12070https://www.acmicpc.net/problem/12071 24/05/21 스몰과 라지 풀이 방식이 거의 유사해서 같은 글로 적어보려고 한다. 문제 접근 방식: 문제 설명에 앞서서 편의 상 선공이 지는 포지션을 Cold position, 선공이 이기는 포지션을 Hot position이라고 부르겠다. 문제의 내용은 Small문제에 들어가면 wizardrabbit님이 번역해놓은 것이 있으므로 이를 참고해보자.https://www.acmicpc.net/board/view/143383 Small의 경우는 제한이 $N = 1, 000$까지이므로, DP배열을 $1,000$까지 선언하여 DP를 돌리면 된다. 이 때 어떤 숫자가 g-num.. 이전 1 2 3 4 다음
