본문 바로가기

정수론

 (37)
[Python] 20302번 민트 초코 https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 24/02/13 자잘한 실수를 많이 해 애를 많이 먹었던 문제입니다. 제가 잘못 접근했던 순으로 문제를 설명하고자 합니다. 문제 접근 방식: 문제에서 주어지는 정보는 간단합니다. 주어진 수식을 순서대로 계산하고, 그 결과가 정수인지 유리수인지 판별하는 것입니다. 파이썬을 사용하고 있다면 가장 흔하게 저지를 수 있는 실수는, 너무 간단한 풀이를 떠올려 구현하는 것입니다. 1. 파이썬에는 eval()이라는 함수가 존재해서, 주어진 수식의 값을 계산해줍니다. 이를 사용하..
[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] 2487번 섞기 수열 https://www.acmicpc.net/problem/2487 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 24/03/21 순열 사이클 분할의 개념을 알고 있으면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 모든 순열(Permutation)은 일정한 사이클들로 "분할"할 수 있다는 개념이 순열 사이클 분할이다. 순열 사이클 분할에 대해서 더 자세히 알고 싶다면 아래 링크를 참고해보자. https://en.wikipedia.org/wiki/Permutation#Cycle_notation ..
[Python] 27295번 선형 회귀는 너무 쉬워 1 https://www.acmicpc.net/problem/27295 27295번: 선형 회귀는 너무 쉬워 1 유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중을 하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 더 어려운 문제를 내 www.acmicpc.net 23/01/30 선형 회귀는 너무 쉬워 시리즈의 첫 번째 문제이다. 간단한 선형 방정식을 풀면 되는 문제다. 문제 접근 방식: 문제의 요구 사항은 $b$가 주어지고 각 데이터들이 주어질 때, $\sum_{i=1}^{n} (ax_i + b - y_i)$가 $0$에 가장 가깝도록 하는 $a$의 값을 구하는 것이다. 가능한 $a$의 값이 여러 개라면 EZPZ를 출력하면 된다. 식을 ..
[Python] 30510번 토마에 함수 https://www.acmicpc.net/problem/30510 30510번: 토마에 함수 첫째 줄에 두 양의 정수 $P$, $Q$가 공백으로 구분되어 주어진다. $(1\le P\le Q\le 100\, 000)$ www.acmicpc.net 24/03/07 이전에 SASA컵을 검수한 적이 있었다. 사실 그때 너무 바빴어서 풀이만 생각하고 정해 코드를 짜지 않았었는데, 이 문제의 해설을 작성해보고자 한다. 문제 접근 방식: 문제를 요약하면 다음과 같다. $x$가 무리수면 $f(x) = 0$ $x$가 $0$이면 $f(x) = 1$ 그 외 $x = \frac{p}{q} ; \mathrm{gcd}(p, q) = 1$이면 $f(x) = \frac{1}{q}$ 임의의 유리수 $\frac{P}{Q}$가 주어질 ..
[Python] 10166번 관중석 https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 24/02/13 실버 1치고는 많은 고민을 하게 한 문제이다. 각 코드 별로 어떠한 흐름을 가지고 생각했는지 적어보고자 한다. 문제 접근 방식: 처음으로 생각한 것은, 보이는 관중석이 어떤 일정한 규칙을 가지고 있어서, 그 규칙이 수식으로 표현 될 것이라는 생각이 들었다. 그 이후에 바로 보인 사실은, $i < j$일때, 반지름 $i$가 반지름 $j$인 원을 가린다면, 그 가리는 관중석의 개수는 ..
[Python] 11688번 최소공배수 찾기 https://www.acmicpc.net/problem/11688 11688번: 최소공배수 찾기 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. www.acmicpc.net 24/01/25 단순한 정수론 문제로, 소인수 분해 코드를 효율적으로 작성한다면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: $a, b, L$의 값이 주어질 때, $\mathrm{lcm}(a, b, c) = L$을 만족시키는 가장 작은 $c$의 값을 구하는 것이 문제의 의도이다. $\mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b), c)$가 성립하므..
[Python] 10407번 2 타워 https://www.acmicpc.net/problem/10407 10407번: 2 타워 2 타워의 높이 H는\[2^{2^{2^{\cdot^{\cdot^{\cdot 2}}}}}\]에서 숫자 2가 나타나는 횟수로 정의된다. 2 타워의 값은 해당 표현식의 값으로 정의된다. 예를 들어, 높이 1의 2 타워 값은 2이고, 높이 2의 2 타워 www.acmicpc.net 24/01/20 수학 문제로, 찍어서 맞출 수도 있으나 여기서는 증명을 소개하도록 하겠다. 문제 접근 방식: 결론만 이야기 하자면, $H = 1$일 때는 나머지가 $2$이고, 그 외에는 $1$이다. 일단 $H=1$일 때는 2타워의 값은 $2$이므로, $3$으로 나눈 나머지가 $2$이다. $2$를 짝수 번 곱하면 그 숫자를 $3$으로 나눈 나머지..

티스토리툴바