본문 바로가기

에라토스테네스의 체

 (8)
[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] 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$원을 넣었을 때, 소수..
[Python] 17394번 핑거 스냅 https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 22/11/18 BFS와 에라토스테네스의 체를 섞은 독특한 문제로, 두 알고리즘을 모두 알고 있다면 어렵지 않게 해결할 수 있는 문제이다. 특히, 이 문제는 1697번 숨바꼭질 문제와 같은 방식으로 방문처리를 하기 때문에 1697번을 해결했었다면 이 문제 또한 쉽게 해결할 수 있을 것이다. 문제 접근 방식: 먼저 목표 범위인 $A$와 $B$의 범위를 보면 $2 \leq A \leq B \leq 100,..
[Python] 4913번 페르마의 크리스마스 정리 https://www.acmicpc.net/problem/4913 4913번: 페르마의 크리스마스 정리 각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 www.acmicpc.net 22/11/13 분명 태그 하나(에라토스테네스의 체)가 보이는 문제여서 접근을 했건만, 2번의 시간초과와 여러 번의 의문의 틀렸습니다를 받고 당황했던 문제이다. 요구하는 선행지식은 누적 합의 개념과 에라토스테네스의 체이다. 문제 접근 방식: 먼저, 구간 내의 소수를 판정해야되고, $L$과 $U$의 범위가 최대 $1,000,000$까지 이므로, 에라토스테네스의 체..
[Python] 25921번 건너 아는 사이 https://www.acmicpc.net/problem/25921 25921번: 건너 아는 사이 첫째 줄에 비용의 최솟값을 출력한다. www.acmicpc.net 22/11/06 대회 도중에는 거의 접근을 가까이했지만 풀지 못했으나, 이후 살짝 고쳐서 맞았습니다를 받은 문제이다. 그래프 문제처럼 보이는 소수 판정 문제로, 참 기발하다고 생각했다. 문제 접근 방식: 음식의 가격의 합을 작게 하려면 최대한 음식을 먹는 횟수가 적어야 할 것이다. 다시 말해, 밥을 먹는 사람들의 번호를 노드, 서로 밥을 먹는 사람들끼리 잇는 것을 간선이라고 한다면, 우리는 이 간선의 개수를 최소한으로 만들어야 한다. 쉽게 이야기하자면 서로 만나서 밥 먹는 횟수가 적어야 된다. 따라서, 이 그래프에서는 사이클이 없어야 된다. ..
[Python] 21919번 소수 최소 공배수 https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 22/09/25 간단한 에라토스테네스의 체 알고리즘을 적용하는 문제로, 그다지 어려운 문제는 아니다. 만약 에라토스테네스의 체 알고리즘을 잘 모르는 상태라면, 먼저 배우기를 권장한다. 문제 접근 방식: 수열들 중에서 소수들을 먼저 골라야 되고, 주어지는 숫자의 크기가 백만 이하이므로, 백만 개의 배열을 불러와 에라토스테네스의 체 알고리즘을 진행하여 소수들을 골라낸다. 이후 이 소수들의 최소공배수를 구하는 것이 우리의 목적이다. 근데 우리는 소수들끼리는 모두 최대공약수가 1이라는 사실을 알고 있다. 때문에 최소 공배수를 구하려면 그냥 그 ..
[Python] 4948번 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 22/09/15 마찬가지로 그룹 채점 현황에 있는 무작위 문제 중 한 문제를 푼 것으로, 기존에 있던 에라토스테네스의 체 코드를 재활용하여 문제를 쉽게 풀었다. 문제 접근 방식: 문제가 n을 입력받으면 n과 2n 사이에 있는 소수의 개수를 출력하는 것이 문제이므로, 에라토스테네스의 체를 구현하면 될 것이라고 생각했다. 에라토스테네스의 체는 다음과 같이 구현했다. 먼저 크기가 정해진 배열을 ..

티스토리툴바