모듈로 곱셈 역원 (5) 썸네일형 리스트형 [Python] 32390번 과녁 맞히기 https://www.acmicpc.net/problem/32390 24/11/17 이전에 KCPC때 검수 못했던 문제 중 하나인데, 이제서야 풀어본다. 사실 그때 한 30분 정도 생각해보다가 답이 안나와서 그냥 GG치고 다른 문제를 봤다. 이제서야 붙잡은 이유는 큰 이유는 없고, 그냥 좀 붙잡으면 풀릴 것 같아서 붙잡았다. 이 문제를 풀기 위해선, 모듈로 곱셈 역원에 대한 지식이 필요하다. 문제 접근 방식: 문제가 뭔가 수능에서 나올법 한 경우의 수 문제랑 비스무리 하다. $M$개의 줄이 있고, 각 줄에는 과녁이 $A_i$개 만큼 달려있다. 나는 과녁을 쏠 때, 각 줄에서 위 또는 아래만 쏠 수 있다.이 문제에서 구하고자 하는 것은 과녁을 쏘는 전체 경우의 수이다. 일단 각 줄 별로 생각을 하면,.. [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] 31478번 포니 양은 놀고 싶어! https://www.acmicpc.net/problem/31478 31478번: 포니 양은 놀고 싶어! 첫 번째 줄에 정수 $A$, $B$, $C$가 주어진다. ($1\leq A < 7$, $1\leq B, C \leq 10^{9}$, $B^C$는 $A$의 배수) 두 번째 줄에 정수 $K$와 $L$이 주어진다. ($0\leq K,L < 7$) www.acmicpc.net 24/04/15 간단한 정수론 문제입니다. 분할 정복을 이용한 거듭제곱에 관한 지식과, 페르마의 소정리에 관한 지식이 있어야 해결할 수 있습니다. 문제 접근 방식: 결국 $A^{B^C}$와 $B^C / A$를 빨리 구하는 문제로 귀결됩니다. 후자는 빠르게 구할 수 있습니다. 결국 $7$일이라는 범위 안에서만 따지는 것이기 때문에 $7$.. [Python] 9343번 랜덤 걷기 https://www.acmicpc.net/problem/9343 9343번: 랜덤 걷기 각 테스트 케이스 마다 음수 좌표를 방문하지 않고 시작점으로 도아오는 랜덤 걷기의 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 23/12/07 누가 봐도 그냥 카탈란 수 문제다. 문제 접근 방식: 누가 봐도 그냥 카탈란 수 문제인데, 이건 제한이 크기 때문에 카탈란 수의 점화식으로 구현하면 안된다. 일반항으로 접근해야 되는데, 모듈로 역원을 활용하여 구현할 수 있다. 파이썬은 모듈로 역원을 pow함수를 통해 쉽게 구할 수 있으니 이를 잘 활용해 보자. 카탈란 수의 일반항은 다음과 같다. $$C_n = \frac{1}{n+1} \binom{2n}{n}$$ 아래는 내가 위.. [Python] 21739번 펭귄 네비게이터 https://www.acmicpc.net/problem/21739 21739번: 펭귄 네비게이터 펭귄은 현재 ($1$, $1$)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 ($2$, $N$)이다. 하지만 누군가에 의해 얼음길이 다 깨져 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 www.acmicpc.net 23/12/06 이것도 카탈란 수임을 알면 매우 쉬운 문제이다. 문제 접근 방식: 이 문제는 카탈란 수 임을 알아내는게 조금 까다롭다. 영 타블로를 잘 알고 있는 사람이라면 이 그림이 $2 \times n$짜리 영 타블로의 개수이고, 이를 계산하면 카탈란 수라는 사실을 알 수 있다. 근데 이건 좀 더 나아간 설명이고, 그림을 살펴보면, "항상" 윗 줄보다 밑 줄의 원소가.. 이전 1 다음
