본문 바로가기

글

 (385)
[Python] 32228번 등차수열 만들기 https://www.acmicpc.net/problem/32228 24/09/15  맷코컵 당시 검수했던 문제 중 하나이다. 알면 보자마자 떠오르는 낚시 문제다. 문제 접근 방식:  문제에서는 주저리 주저리 적혀져 있는데, 오일러 파이 함수의 값을 출력하면 끝이다. 그러면, 결론이 왜 그렇게 나오는지에 대해 알아야 한다. 문제에서 주어진 것 처럼 mod $M$에서의 등차수열을 직접 구하는 방식으로 $K$값을 짜내려고 한다면 곤란하다. $N$의 제한과 $M$의 제한이 꽤나 크기 때문이다. $A_i$와 $M$이 서로소라는 조건, 모두 같은 $K$제곱을 하여 $A_{i}^{K}$로 만들고 mod $M$과 엮는다는 점을 유의깊게 생각하면 쉽게 파악할 수 있다. 이 $K$의 값이 $\varphi (M)$이 된다..
[Python] 32229번 B끼B끼 A끼A끼 수열 찾기 https://www.acmicpc.net/problem/32229 24/09/14  맷코컵 때 검수했던 문제 중 하나이다. 지문을 해석하는 재미가 있는 문제다. 그것과는 별개로, 제목이 별로다. 문제 접근 방식:  일단, 문제 해석을 하면 이 문제의 80%는 해결한 것과 다름이 없다.  먼저, 집합 $S$의 정의를 유의 깊게 보자. 문제에서 주어지는 입력은 $A, B, N$이다. $S$는 순서쌍 $(x, y)$들의 모임인데, 작은 것이 $x$이고 큰 것이 $y$이다.($x  또한, 이 둘의 차이는 $A$또는 $B$이며, $x$는 최소 $1$, $y$는 최대 $N$의 값을 가질 수 있다.  이제 수열 $P$의 정의를 유의 깊게 보자. 수열 $P$에는 $1$부터 $N$까지의 모든 수가 최소 하나씩 있고 $..
[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] 32230번 현대모비스 첨단 운전자 보조 시스템 https://www.acmicpc.net/problem/32230 24/09/10  내가 출제한 문제고, 에디토리얼이 나오려면 좀 걸릴 것 같아서 미리 내 문제만 먼저 해설을 작성해보고자 한다.  문제 접근 방식:  문제의 요구 사항은 안전 영역의 최솟값을 구하는 것이다. 서브태스크별로 할 수 있는 풀이를 적고자 한다. 서브태스크 1문제를 잘 읽고 $N \geq 3$일때 볼록 다각형이 만들어지고, 그렇지 않은 경우 볼록 다각형이 만들어지지 않음을 파악한다. 따라서, $0$을 출력하면 받을 수 있다. 서브태스크 2 문제의 핵심 부분이다. 문제에서 유의 깊게 관찰할 수 있는 부분들은 $10^{-9}$과 같은 빡빡한 오차, $1$초와 같은 수상한 제한, 수상하게 큰 좌표 제한 등이 존재한다. 가장 나이브하게..
[Python] 1199번 오일러 회로 https://www.acmicpc.net/problem/1199 24/09/01  오일러 경로 기본 문제이다. 알고리즘은 간단했으나 시간이 좀 빡빡해서 몇 번의 최적화를 거친 후에야 맞았습니다를 받을 수 있었다. 문제 접근 방식:  무방향 연결 그래프에서 오일러 경로는 정점의 차수가 홀수인 정점이 $0$개이거나 $2$개일 때 만들어 질 수 있다. 차수가 홀수인 정점이 $0$개인 경우, 어느 점에서 시작을 하던 간에 다시 그 점으로 돌아오는 오일러 "회로"를 만들 수 있다. 차수가 홀수인 정점이 $2$개인 경우, 차수가 홀수인 $A$ 정점에서 시작하여 차수가 홀수인 $B$ 정점으로 도착하는 오일러 경로를 만들 수 있다. 이 문제는 오일러 "회로"가 만들어지는 조건을 물어보고 있으며, 그것이 가능한 경우 ..
[Python] 19171번 Euclid https://www.acmicpc.net/problem/19171 24/07/29  어제부터 잡았던 문제인데, 사실 개뻘짓을 하고 있음을 깨달아서 그냥 어이 없어서 적어본다. 문제 접근 방식:  문제에서 요구하는 것은, 세 점 $p_1, p_2, p_3$가 주어지고 어떤 점 $p$에 대하여, $p$와 세 점 사이의 거리의 합이 최소가 될 때, 그 거리의 합을 구하는 것이다. $p_1, p_2, p_3 = (x_1, y_1, z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)$라고 둔다면 다음과 같은 함수를 최소화하는 문제로 바뀐다. $$\begin{align} f(x, y, z) &= \sqrt{(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2} \\ &+ \sqrt{(x-..

티스토리툴바