정수론 (37) 썸네일형 리스트형 [Python] 32840번 Triangle https://www.acmicpc.net/problem/32840 24/11/26 ICPC본선 당시에 파이썬으로 구현해서 맞은 문제다. 약간의 많은 조건 분기가 들어가는데, 이건 사람마다 갈릴 수 있는 부분이라서 구현이 어렵다고 하기에는 조금 힘들 것 같다. 문제 접근 방식: 결론적으로 이야기 하면 변 위에 있는 정수 격자점 중 꼭짓점과 가장 가까운 두 점만 보면 된다. 즉, 봐야하는 점이 변에 대해서 2개 이므로, 총 8가지 경우의 수에 대하여 브루트포스를 돌리면 된다. 이 이유는 아핀변환을 곰곰히 생각해보면 된다. 이전에 아핀변환에 관련된 문제를 내서 그런지, 이에 대한 아이디어는 금방 떠올랐다. 점 2개를 고정하고 하나를 움직이는건 아핀변환에 해당한다. 기존 삼각형의 넓이에서 변화가 가장 적어.. [Python] 21870번 시철이가 사랑한 GCD https://www.acmicpc.net/problem/21870 24/11/04 단순한 분할정복 문제다. 문제 접근 방식: 얼핏 보면 시간제한이 1초고, 나이브하게 돌리면 빡빡할 것이라고 생각이 들 것이다. 우리는 왼쪽과 오른쪽으로 항상 배열이 나뉨을 관찰할 수 있다. 왼쪽 배열의 값들의 gcd + 오른쪽 배열의 최대 혹은 오른쪽 배열의 값들의 gcd + 왼쪽 배열의 최대 중 가장 큰 값이 우리가 원하는 값임을 확인할 수 있다. 오른쪽 배열의 최대 혹은 왼쪽 배열의 최대 또한 분할 정복을 통해 계속 재귀적으로 구할 수 있으므로, $\mathcal{O}(N \log N)$만에 문제를 해결할 수 있다. DP로 값을 저장하지 않아도 충분히 돌아감을 확인할 수 있다.(오히려 값을 저장하면 저장하는 시간때.. [Python] 32653번 흑백 요리사 https://www.acmicpc.net/problem/32653 24/11/20 간단한 정수론 문제다. 문제 접근 방식: 하나의 고기 앞/뒷면을 모두 익히기 위해서는 최소 $2x_i$만큼의 시간이 필요하다. 모든 고기를 동시에 다 익혀야 하므로, $2x_i$들의 최소 공배수만큼 익히는 것이 최소 시간이 된다.아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 32653번 흑백 요리사# 정수론import sysinput = sys.stdin.readlinefrom math import lcmN = int(input())A = list(map(lambda x: 2*int(x), input().split()))print(lcm(*A)) [Python] 32390번 과녁 맞히기 https://www.acmicpc.net/problem/32390 24/11/17 이전에 KCPC때 검수 못했던 문제 중 하나인데, 이제서야 풀어본다. 사실 그때 한 30분 정도 생각해보다가 답이 안나와서 그냥 GG치고 다른 문제를 봤다. 이제서야 붙잡은 이유는 큰 이유는 없고, 그냥 좀 붙잡으면 풀릴 것 같아서 붙잡았다. 이 문제를 풀기 위해선, 모듈로 곱셈 역원에 대한 지식이 필요하다. 문제 접근 방식: 문제가 뭔가 수능에서 나올법 한 경우의 수 문제랑 비스무리 하다. $M$개의 줄이 있고, 각 줄에는 과녁이 $A_i$개 만큼 달려있다. 나는 과녁을 쏠 때, 각 줄에서 위 또는 아래만 쏠 수 있다.이 문제에서 구하고자 하는 것은 과녁을 쏘는 전체 경우의 수이다. 일단 각 줄 별로 생각을 하면,.. [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] 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] 27852번 Kruskal https://www.acmicpc.net/problem/27852 24/05/17 오랜만에 스프라그-그런디 정리 문제를 해결했기에 글로 작성해본다. 님 게임의 변형 문제로, 어떻게 해야 님 게임으로 치환할 수 있을지를 고민해볼 수 있는 좋은 문제이다. 문제 접근 방식: 문제에서 제시하는 상황은 다음과 같다. 일반적인 님 게임과 비슷하게, 돌 더미들이 여러 개 주어져 있다. 대신, 한 플레이어가 $1$개부터 $K$개까지 돌을 가져갈 수 있으며, 승리 조건이 어느 한 플레이어가 "소수"개수에 해당하는 돌 더미를 만들게 되면 즉시 이기게 되는 게임으로 바뀌었다. 두 플레이어가 최선의 플레이를 진행한다고 할 때, 누가 이길 지를 판별하는 것이 문제의 요구조건이다. 님 게임의 변형으로 돌 개수의 제한을 두는.. 이전 1 2 3 4 5 다음