본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 15703번 주사위 쌓기 https://www.acmicpc.net/problem/15703 15703번: 주사위 쌓기 아래 설명에서 k개의 주사위가 쌓여져 있고, 위에서부터 적혀있는 정수가 s1, s2, ..., sk인 주사위 탑을 (s1, s2, ..., sk)로 표현했다. 예제 1의 경우에는 주사위 탑 1개를 만들 수 있다. (1, 2, 4, 5) 또는 ( www.acmicpc.net 23/05/25 구현을 조금 요하는 그리디 문제이다. 문제 접근 방식: 문제 요약을 하면 다음과 같다. 주사위가 주어져 있고, 하나의 주사위의 모든 면에는 같은 눈금이 적혀있다. 이런 주사위들을 모아 주사위 탑을 쌓고자 하는데, 한 주사위에 적힌 눈금이 $5$라면, 그 주사위 위에는 $5$개를 넘어서 주사위를 쌓을 수 없다고 한다. 이럴 때,..
[Python] 8845번 Gra https://www.acmicpc.net/problem/8845 8845번: Gra Dla każdej konfiguracji początkowej w osobnej linii wypisz "W", jeśli Hektor wygra grę przy danym ustawieniu, "P" w przeciwnym przypadku. www.acmicpc.net 23/05/31 스프라그-그런디 정리가 적용되는 게임은 DAG(Directed Acyclic Graph)로 모델링 될 수 있다는 사실을 알고 있다면 쉽게 풀 수 있는 문제이다. 비슷한 문제들로 다음과 같은 문제들을 추천하니, 풀어본다면 좋은 연습이 될 것이다. https://www.acmicpc.net/problem/10363 10363번: Circ..
[Python] 16887번 루트 님 게임 https://www.acmicpc.net/problem/16887 16887번: 루트 님 게임 첫째 줄에 돌 더미의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 둘째 줄에 돌 더미에 포함된 돌의 개수 Ai(1 ≤ Ai ≤ 1,000,000,000,000)가 주어진다. www.acmicpc.net 23/04/06 스프라그-그런디 문제로, 사실 스프라그-그런디 정리를 곁들인 수학 문제라고 봐도 무방한 문제다. 그런디 수를 구하는 경계가 조금 구하기 귀찮기 때문에 난도가 높은 것이라고 생각한다. 하지만 개인적으로 플레티넘 1을 받을 정도의 난이도는 아니라고 생각하는 문제다. 문제 접근 방식: 문제에서 주어진 것 처럼 그대로 구현하면 당연히 시간 초과가 날 것이다. 이는 직접 해보면 잘 알 것이다.. ..
[Python] 19114번 Master Zhu and Candies (증명 추가 필요) https://www.acmicpc.net/problem/19114 19114번: Master Zhu and Candies Master Zhu puts $n$ heaps of candies on the table. Two players are playing the following game: on their turn, each player can either pick any positive number of candies from the same heap, or split some heap into three smaller non-empty heaps. Player who p www.acmicpc.net 23/05/03 전형적인 스프라그-그런디 정리 문제로, 문제에서 주어지는 그대로 착실하게 구현하면 된..
[Python] 스프라그-그런디 정리 활용 문제 모음 2022.11.01 - [백준 문제 풀이] - [Python] 13034번 다각형 게임 / 16187번 Game on Plane [Python] 13034번 다각형 게임 / 16187번 Game on Plane https://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다 lighter.tistory.com 2022.11.01 - [백준 문제 풀이] - [Python] 16895번 님 게임 3 / 7685번 Nim [Python] 16895번 님 게임 3 / 7685번 Nim https://www.acmicpc.net/probl..
[Python] 27306번 DAGame https://www.acmicpc.net/problem/27306 27306번: DAGame 첫 번째 줄에 노드의 개수를 나타내는 정수 $N$ ($2 \le N \leq 500$), 간선의 개수를 나타내는 정수 $M$ ($1 \leq M \leq 100\,000$)이 주어진다. 두 번째 줄 부터 $M$개의 줄에 서로 다른 두 정수 $p$, $q$ ($1 \leq p$ www.acmicpc.net 23/05/03 스프라그-그런디 정리에 대한 이해도가 있어야 해결할 수 있는 문제다. 몇몇 사람들은 스프라그-그런디 정리의 문제를 풀 때 결과만 외우고 그냥 XOR계산만 적용해서 문제를 푸는 경우가 좀 있다고 생각한다. 나도 스프라그-그런디 정리를 적용한 문제를 처음 풀었을 때, 이해 없이 결과만 받아들이고 문..
[Python] 9066번 금고 https://www.acmicpc.net/problem/9066 9066번: 금고 어떤 금고가 N × N 개의 격자에 모두 한 개씩의 손잡이를 가지고 있다. 모든 손잡이는 수직(|), 또는 수평(-), 이 두 가지 상태밖에 없으며 이 손잡이를 돌려서 수직, 수평으로 만들 수 있다. 각 손 www.acmicpc.net 23/03/20 체감 상 플레티넘 5보다 어려웠다고 느껴졌던 문제이다. 나는 선형대수학적 지식을 이용하여 문제를 해결했다. 시간복잡도 상으로 더 짧게 걸리는 풀이도 있긴 하나, 결국 이 풀이 또한 내가 풀었던 방법과 본질적으로는 같은 방법으로, 이를 증명하기 위해서는 선형대수학적 지식이 수반되어야 한다. 때문에 이 글은 선형 대수학의 내용 중 '체'와 '벡터공간'에 대한 지식과, 연립 일차..
[Python] 9718번 Matrix Transformation https://www.acmicpc.net/problem/9718 9718번: Matrix Transformation The first input line contains a positive integer,n, indicating the number of matrices (test cases). Each matrix starts with a line containing R(2≤R≤30) and C(2≤C≤30) separated by a single space. Each of the next R lines contains C integers. Each of www.acmicpc.net 23/03/14 불변량의 개념을 숙지한 상태라면 쉽게 접근할 수 있는 문제이다. 만약 이 문제를 크기 제한($2 \leq..

티스토리툴바