기록방

👉 문제링크 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 🔸 문제 분석 🔸 정수 N을 연속된 소수의 합으로 만드는 경우의 수를 출력한다. 🔸 문제 풀이 🔸 소수를 구하기 위해 에라토스테네스의 체를 사용한다. 연속된 수의 합에서 경우의 수를 따지므로 투 포인터를 이용해 배열을 이동하며 N이 만들어지는지 확인한다. 🔸 코드 🔸 import java.io.*; import java.util.ArrayList; public class Main { public static void main(String[] args) throws IOException { // Input BufferedReader br = new BufferedRead..

👉 문제링크 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 🔸 문제 분석 🔸 최대 10만개의 서로 다른 수가 적힌 카드가 있다. 이때 수는 1~100만 사이의 정수이다. 카드들을 서로 결투를 벌여서 나누어 떨어지면, 나누는 수는 +1, 나누어진 수는 -1 점을 받는다. 모든 카드들을 결투시켜 최종 점수를 출력한다. 🔸 문제 풀이 🔸 N이 10만이므로 O(NlogN)로 비교하면, 100억번으로 제한 시간인 1초를 초과하게 된다. 에라토스테네스의 체를 활용해서 소수가 아닌, 카드 숫자의 배수 인덱스만 확인해서 결투를 진..

👉 문제링크 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 🔸 문제 분석 🔸 주어진 범위에서 1보다 큰 수의 제곱수로 나누어 떨어지지 않는 수의 개수를 출력한다. 최소값이 1부터 1조, 최대값은 최소값부터 100만을 더한 값까지 주어진다. 🔸 문제 풀이 🔸 min과 max의 값이 1조까지 크게 주어지므로 long으로 받야아 한다. 제곱수를 확인하기 위해 에라토스테네스의 체 알고리즘을 사용한다. 배열의 크기를 max-min+1 만큼 차이로 선언한다. 제곱수의 배수를 max까지 계산하며 에라토스..

👉 문제링크 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 🔸 문제 분석 🔸 소수를 구한 후 오름차순으로 팰린드롬을 찾아 출력한다. 🔸 문제 풀이 🔸 N이 100만까지 입력되는데, 여유있게 1000만까지 소수를 구한다. 팰린드롬은 수를 char배열로 변환한 뒤 투포인터로 판단한다. 🔸 코드 🔸 import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

👉 문제링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 소수의 N제곱 (N>2)의 수를 거의 소수라고 한다. A이상 B이하의 거의 소수의 개수를 출력한다. (1