본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 32518번 대충 블록에서 영혼 탈출시키는 게임 https://www.acmicpc.net/problem/32518 24/11/08  간단한 탑다운 DP다. 바텀업으로는 해결할 수 없다. 문제 접근 방식:  처음에는 $N$의 제한이 $10^{18}$인 것을 보고 DP가 아니라 하나의 완성된 수식으로 나올 줄 알고 100까지의 바텀업 DP를 돌렸다. 뚜렷한 규칙이 보이지 않아서, 수학적으로 해결하는 것은 그만두고, 다른 해결방법이 있는지 모색하기 위해 어떤 경우에 최댓값이 나오고, 그때 분할되는 경우가 어떤 경우인지를 모두 찾는 코드를 작성했다. $N-2$가 3으로 나눠진다면, $((N-2)//3, (N-2)//3, (N-2)//3)$과 같이 분할된다.  예를 들어, 8과 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오는데, 각 체인의 길이는 ..
[Python] 32387번 충전하기 https://www.acmicpc.net/problem/32387 24/10/06   KCPC 당시, 파이썬으로 검수했던 문제다. 다양한 풀이가 있어서 나름 연습해보기 적절한 문제라고 생각한다. 문제 접근 방식:  문제의 요구 사항은 다음과 같다. 크기가 $N$인 Bool 배열 $A$가 주어지고, 두 종류의 쿼리가 주어진다. 쿼리의 개수는 최대 $10^6$개이며, 배열의 최대 크기는 $10^6$이다. 또한, 배열의 초기 상태는 모두 False로 초기화되어있는 상황이다. 1번 쿼리는 인덱스 $i$가 주어진다. $i$보다 크거나 같은 인덱스 $k$중에서, $A[k]$ = False로 되어있는 가장 작은 인덱스를 True로 바꾸는 것이다. 만약 이것이 불가능하다면 $-1$을 출력한다. 2번 쿼리는 인덱스 $..
[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$초와 같은 수상한 제한, 수상하게 큰 좌표 제한 등이 존재한다. 가장 나이브하게..

티스토리툴바