알고리즘 (368) 썸네일형 리스트형 [Python] 12848번 막대기 게임 https://www.acmicpc.net/problem/12848 24/05/16 간단한 스프라그-그런디 정리 응용 문제로, 게임판 분할에 관한 개념을 알고 있으면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 막대기를 게임판 위에 더 이상 둘 수 없는 사람이 지는 게임이다. 다행히도 막대기는 가로 모양 밖에 존재하지 않아서, 각 행 별로 게임이 분리된다는 사실은 쉽게 알 수 있다. 또한, 장애물이 있는 곳에는 막대기를 둘 수 없다는 제한 조건 때문에, 장애물이 놓여 있는 곳 별로 게임이 분리된다는 사실 또한 쉽게 알 수 있다. 따라서, 각 행 별로, 각 막대기가 놓여진 곳 별로 게임을 분리하여, 각 게임 별 그런디 수를 구하면 된다. $n > k$이고, 길이 $n$짜리 게임 판이 주어질 때, .. [Python] 28218번 격자 게임 https://www.acmicpc.net/problem/28218 24/05/24 간단한 게임 DP 문제이다. 최근 게임 이론 문제들을 많이 풀어보고 있는데, 꽤나 재미있다. 문제 접근 방식: 접근 방식은 나이브한 게임 DP이다. 골드 난이도에서 진행되는 게임 DP는 스프라그-그런디 정리가 섞이는 경우가 없기 때문에, 그냥 누가 이기는지 지는지에 대한 여부만 DP배열에 저장해주면 된다.(즉, 님버를 굳이 저장할 필요가 없다.) 선공이 지는 포지션을 0으로 저장하고, 선공이 이기는 포지션을 1로 저장하자. 내가 어떤 행동을 통해 말을 움직이면, 움직여진 게임 판 그대로 상대방이 처음부터 시작하는 것과 같다. 즉, 내가 어떤 행동을 통해 말을 움직여서 나의 턴을 끝내면, 그 상태 그대로 상대방이 선공으.. [Python] 8170번 Pebbles (추후 보강 예정) https://www.acmicpc.net/problem/8170 24/05/19 스프라그-그런디 문제로, 증명하기가 꽤나 어렵고 규칙을 발견하는 것도 쉽지 않은 문제인 것 같다. 나는 이 문제를 해결하기는 했지만, 왜 그렇게 나오는지에 대한 증명은 하지 않아서, 추후에 증명을 하게 된다면 보강해서 작성할 예정이다. 문제 접근 방식: 처음에 문제를 접근한 방식은 나이브한 탑-다운 DP였다. 가지고 있는 현재 조약돌의 전체 상황을 튜플로 저장하여, 그 상황을 딕셔너리에 집어넣는 풀이였다. 당연히 시간초과를 받을 수 밖에 없었는데, 잘 생각해보면 돌 더미의 개수가 최대 $1,000$개이고, 내가 어떤 게임판의 상황에서 할 수 있는 행동 또한 정말 많기 때문에 시간초과가 날 수밖에 없다. 그래서 규칙을 찾.. [Python] 5981번 Cow Checkers https://www.acmicpc.net/problem/5981 24/05/23 모르면 쳐맞는 종류의 게임 이론 문제인 것 같아서 따로 정리해야겠다, 싶어 정리해본다. 문제 접근 방식: https://en.wikipedia.org/wiki/Wythoff%27s_game Wythoff's game - WikipediaFrom Wikipedia, the free encyclopedia Two-player mathematical subtraction game Wythoff's game is played with two piles of counters Wythoff's game is a two-player mathematical subtraction game, played with two piles of .. [Python] 31687번 Trokut https://www.acmicpc.net/problem/31687 24/05/18 스프라그-그런디 정리 문제이다. 약간 웰노운 성이 있는 것 같아서, 정리해보면 좋을 것 같아 글을 써본다. 문제 접근 방식: 문제의 접근 방식은 이전에 내가 글로 작성했던 다각형 게임과 동일하다. 심지어, 해당되는 게임조차 같다. 근데 다각형 게임의 코드를 그대로 복붙하면 시간초과를 받는다.2022.11.01 - [알고리즘/백준 문제 풀이] - [Python] 13034번 다각형 게임 / 16187번 Game on Plane [Python] 13034번 다각형 게임 / 16187번 Game on Planehttps://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이.. [Python] 19778번 Игра https://www.acmicpc.net/problem/19778 24/05/20 그룹 연습 문제로 풀었던 문제다. 간단한 게임 이론 + 구현 문제다. 최적의 전략을 생각하는 것이 그다지 어렵지는 않지만, 이를 실제로 구현하는 것이 전략을 생각하는 난이도에 비해서 조금 까다로운 편이다. 골드 5에 비해 난이도가 낮다고 생각이 되어서 낮게 측정했다. 문제 접근 방식: 러시아어로 되어 있는 문제이기 때문에 번역을 하면 다음과 같이 번역할 수 있다. 문제 번역:체육 수업 시간에 1학년 페티야와 바샤가 흥미로운 게임을 하고 있습니다. 남학생들 앞에 높이가 다른 $n$개의 기둥이 일렬로 서 있습니다. 남학생들은 $m$개의 반지를 가지고 번갈아 가며 기둥에 던지는데, 기둥에 이미 반지가 있으면 이 기둥에 반지.. [Python] 27852번 Kruskal https://www.acmicpc.net/problem/27852 24/05/17 오랜만에 스프라그-그런디 정리 문제를 해결했기에 글로 작성해본다. 님 게임의 변형 문제로, 어떻게 해야 님 게임으로 치환할 수 있을지를 고민해볼 수 있는 좋은 문제이다. 문제 접근 방식: 문제에서 제시하는 상황은 다음과 같다. 일반적인 님 게임과 비슷하게, 돌 더미들이 여러 개 주어져 있다. 대신, 한 플레이어가 $1$개부터 $K$개까지 돌을 가져갈 수 있으며, 승리 조건이 어느 한 플레이어가 "소수"개수에 해당하는 돌 더미를 만들게 되면 즉시 이기게 되는 게임으로 바뀌었다. 두 플레이어가 최선의 플레이를 진행한다고 할 때, 누가 이길 지를 판별하는 것이 문제의 요구조건이다. 님 게임의 변형으로 돌 개수의 제한을 두는.. [Python] 21772번 가희의 고구마 먹방 https://www.acmicpc.net/problem/21772 24/05/14 업다운 랜디를 하다가 만난 문제이다. 처음에는 BFS로 접근할까 하다가 DFS로 방향을 틀어 접근했다. 문제 접근 방식: BFS로 접근할 수도 있다. 그 이유는 최대 10번을 탐색하고 한 번 할 때 4방향을 탐색하기 때문에 $4^{10}$번만 탐색하면 충분하고, 이는 시간 안에 들어오기에 충분하기 때문이다. 하지만 DFS로 접근하는 것이 더 쉬울 것 같아서 DFS로 접근했다. 무의식 중에 재귀 깊이를 10만으로 늘린 코드를 작성하긴 했지만, 사실은 10번만 탐색하기 때문에 그렇게까지 깊게 늘리지 않아도 되었던 것 같기도 하다. DFS를 진행하는데, 들어간 자리에 고구마가 있으면 고구마를 먹었다는 표시로, 고구마 글자를.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 46 다음