정수론 (37) 썸네일형 리스트형 [Python] 31216번 슈퍼 소수 https://www.acmicpc.net/problem/31216 31216번: 슈퍼 소수 소수는 수학을 사랑하는 누구에게나 매우 중요한 개념입니다. $1$보다 크면서 약수가 $1$과 자기 자신뿐인 자연수를 소수라고 부릅니다. 흐즈로는 소수 중에서도 더욱 특별한 소수가 있다고 생각 www.acmicpc.net 24/01/08 간단한 소수 판정 응용 문제다. 문제 접근 방식: 문제는 매우 간단하다. 소수를 오름 차순으로 나열하여 $k$번째 소수가 있을 때, 이 $k$가 소수라면 그 소수를 슈퍼 소수라고 한다. 우리의 목적은 $n$이 주어지면 $n$번째 슈퍼 소수를 찾는 것이 우리의 목적이다. 여기서 주어지는 $n$은 최대 $3,000$까지이다. $100$만 이하의 소수의 개수는 $78,498$개이므로, .. [Python] 27172번 수 나누기 게임 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 23/12/05 기존 에라토스테네스의 체 알고리즘을 응용한 문제로, 정확히 말하면 체의 원리를 이용한 문제여서 조금 신선하다고 할 수 있다. 클래스 5에도 있는 교육적인 문제이니, 안보고 해결하면 좋을 문제인 것 같다. 문제 접근 방식: 어떤 수가 다른 수의 약수가 되면, 그 수는 점수를 얻는 방식이다. 예를 들어 $3$과 $12$가 서로 게임을 한다고하면 $3$은 1점을 얻고 $12$는 1점을 잃는다... [Python] 17633번 제곱수의 합 (More Huge) https://www.acmicpc.net/problem/17633 17633번: 제곱수의 합 (More Huge) 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 1,000,000,000,000,000,000이다. www.acmicpc.net 23/12/05 처음으로 푼 다이아3 문제이다. 높은 수학적 지식을 요구하기 때문에 사실상 혼자 이 문제를 관찰 만을 통해 풀어낸다는 건 불가능에 가깝다고 생각한다. 다만 이 문제에서 요구하는 정수론적 지식을 이미 갖추고 있는 사람이라면 다이아 3이라는 난이도에 비해 쉽게 문제를 해결할 수 있을 것이라고 생각한다. 문제 접근 방식: 먼저, 이 문제는 밀러-라빈 소수 판별법과 폴라드-로 소인수 분해 알고리즘을 구현.. [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$짜리 영 타블로의 개수이고, 이를 계산하면 카탈란 수라는 사실을 알 수 있다. 근데 이건 좀 더 나아간 설명이고, 그림을 살펴보면, "항상" 윗 줄보다 밑 줄의 원소가.. [Python] 4563번 리벤지 오브 피타고라스 https://www.acmicpc.net/problem/4563 4563번: 리벤지 오브 피타고라스 피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다. A2 + B2 = C2 세 변의 길이가 모두 자 www.acmicpc.net 23/09/07 정수론적 지식을 요구하는 문제로, 주어진 수의 범위에 대해서 어떻게 효율적인 시간으로 판별할 수 있을지 생각해야되는 문제이다. 문제 접근 방식: 당연히 문제에서 요구하는 바를 나이브하게 접근하면 주어지는 수의 범위가 매우 크기 때문에 시간초과를 받을 가능성이 매우 크다. 문제에서 요구하는 바를 다시 상기시켜보자. $A < B$이고, $A$의 값이 최대 .. [MatKor] Math is difficult 문제 수학을 좋아하는 하늘이는 수학을 싫어하는 재우에게 문제를 냈다. $i \in \mathbb{N}$과 $\alpha , \beta \in \mathbb{N}$에 대하여 $0 < a_i < a_{i+1}$와 $\alpha a_i < a_{i+2}$, 그리고 $a_{i+2} \equiv \alpha a_i (\mathrm{mod} \ \beta a_{i+1})$, $a_i \in \mathbb{N}$을 만족하는 수열 $\{ a_i \}$가 있다. 이때 자연수 $N$이 주어질 때, 위의 조건을 만족하는 수열 중 $a_N$을 최소로 만드는 수열을 $f(N) = \{ a_1, a_2, \cdots , a_N \} $라고하자. 또한, 이러한 $f(N)$에 대하여 원소의 합을 $S(N) = \sum_{i = 1}.. [Python] 2421번 저금통 https://www.acmicpc.net/problem/2421 2421번: 저금통 홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다. 홍태석은 www.acmicpc.net 23/03/12 전형적인 2차원 DP문제로, 현재 상태를 잘 정의하고 점화식을 세우면 쉽게 해결할 수 있다. 문제 접근 방식: 문제를 보고 처음에 발견한 사실은, 첫번째 저금통에 돈을 넣거나 두번째 저금통에 돈을 넣거나 둘 중 하나의 상태로만 갈 수 있다는 사실을 알아냈다. 이를 통해 $\mathrm{DP}[i][j]$ $=$ 첫번째 저금통에 $i$원을 넣고, 두번째 저금통에 $j$원을 넣었을 때, 소수.. 이전 1 2 3 4 5 다음
