알고리즘/백준 문제 풀이 (338) 썸네일형 리스트형 [Python] 13172번 Σ https://www.acmicpc.net/problem/13172 24/05/29 클래스에 있던 문제 중에 하나로, 간단한 정수론 문제이다. 문제 접근 방식: 친절하게도, 문제에 대한 답이 다음과 같이 써져있다. $$\frac{S_1}{N_1} + \frac{S_2}{N_2} + \cdots + \frac{S_M}{N_M}$$ 이를 그대로 구현해주면 된다. 이때, 답은 기약분수로 나타내야 하므로, $S_i$와 $N_i$를 입력받을 때마다, $\text{gcd}(S_i, N_i)$로 두 수를 나눠준다. 또한, 모듈로 역원은 파이썬에서는 pow함수의 지수부분에 -1을 넣음으로써 쉽게 구할 수 있으므로 이를 활용하면 쉬워진다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 .. [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.. [Python] 3878번 점 분리 https://www.acmicpc.net/problem/3878 23/10/06 이전에 볼록 껍질 문제를 쭉 푼 적이 있었는데, 그 때 해결 했던 문제 중 하나이다. 흥미로운 문제라고 생각되어 기록으로 남겨보고자 한다. 문제 접근 방식: 문제의 요구 사항은 검은 점과 흰 점을 오직 하나의 직선만으로 서로 분리할 수 있는지 판단하는 것이다. 검은 점끼리를 고무줄로 감싸고, 흰 점끼리를 고무줄로 감쌌을 때, 두 고무줄이 겹치지 않으면 가능하다고 판단했다. 여기서 볼록껍질이라는 말을 사용하지 않은 이유는 고무줄이라는 용어가 더 적합하다고 생각했기 때문이다. 볼록껍질은 고무줄이라는 말을 온전히 대변하지 않는다. 예를 들어, 두 점만 있는 경우 볼록 껍질을 정의하기가 어려운데, 고무줄은 정의할 수 있다. 한.. [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개의 꼭짓점으로 이.. 이전 1 ··· 4 5 6 7 8 9 10 ··· 43 다음