게임 이론 (34) 썸네일형 리스트형 [Python] 7824번 Playing With Stones https://www.acmicpc.net/problem/7824 25/06/26 전형적인 스프라그-그런디 정리 문제이다. 플레티넘 200문제를 달성하기 위해 풀었던 문제들 중 하나이다. 문제 접근 방식: 문제가 영어로 되어 있기 때문에, 해석을 하자면 다음과 같다. 두 사람이 돌을 제거하는 게임을 함.$N$개의 돌 무더기가 주어져 있으며, 각각의 무더기에는 $a_1, a_2, \dots, a_n$개의 돌이 있음.자기 차례에 플레이어는 하나의 무더기에서 최소한 $1$개 이상의 돌을 제거해야하며, 해당 무더기의 돌 개수의 절반 이하만 제거할 수 있음.이때 돌을 제거할 수 있는 선택이 더 이상 없는 플레이어가 짐.두 사람이 최적으로 플레이 할 때, 선공이 이긴다면 "YES", 그렇지 않다면 "NO"를 출.. [Python] 10435번 만칼라 https://www.acmicpc.net/problem/10435 25/06/14 개인적으로 현재 난이도보다 한단계 높은 플레티넘 5정도의 난이도로 느껴진 문제였다. 이전에 북마크에 담아두고 고민하다가 못풀었던 문제인데, 다른 블로그 글을 확인해서 힌트를 얻고 해결했다. 게임 이론과 해 구성하기가 담겨있는 좋은 문제인 것 같다. 문제 접근 방식: 문제를 해결하기 위해서는 2가지 핵심 아이디어를 알아야 한다. 1. 구슬이 $N$개일 때 이기는 상태에서 어떤 "액션"을 취하면 구슬이 $N-1$개일 때 이기는 상태로 바뀐다. 2. "액션"을 취하면 $k$번째에 있던 $k$개의 돌들은 모두 없어지고, $1$번째부터 $k-1$번째의 돌 개수는 한 개씩 증가한다. 어떤 "액션"을 취한 뒤에도 턴을 이어나가려.. [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진법 위에서의 가우스 소거법에 대한 지식. 먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다. 이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다.. 이전 1 2 3 4 5 다음
