Traveling Programmer

문제https://www.acmicpc.net/problem/1456풀이(38분)import java.io.*;import java.util.*;public class Main { static boolean isPrime[] = new boolean[10000001]; // 문제에서 제시된 범위의 제곱근까지 static ArrayList list = new ArrayList(); // 소수를 저장할 리스트 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..

문제https://www.acmicpc.net/problem/3896풀이(17분)import java.io.*;import java.util.*;public class Main { // 소수의 리스트를 먼저 구해두자. // 만약 소수의 리스트에 포함되어 있다면 -> 0을 바로 출력한다. // 포함되어있지 않다면, 자기보다 큰 첫번째의 소수값과 인덱스를 찾는다. // 23과 29 사이에 예를 들어, 27이 k였다면 양쪽으로 4 + 2를 구하면 된다.(27 - 23) + (29 - 27) // 10의 경우 3 + 1 -> (10 - 7) + (11 - 7) public static void main(String[] args) throws IOException { ..

문제https://www.acmicpc.net/problem/5636풀이(17분)import java.io.*;import java.util.*;public class Main { static boolean[] isPrime = new boolean[100001]; static List primeList = new ArrayList(); public static void isPrime(){ // 100,000까지의 소수 먼저 확인 Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; for(long i = 2; i 문제 풀이 전략 초기에 255자리의 문자열에 대해 어떻게 ..

문제https://www.acmicpc.net/problem/1124풀이(25분)import java.io.*;import java.util.*;public class Main { static boolean[] prime; // 소수 확인 배열 static int[] dp; // dp 메모이제이션 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); ..

문제https://www.acmicpc.net/problem/9020풀이(22분)import java.awt.Point;import java.util.*;import java.io.*;public class Main{ static ArrayList prime = new ArrayList(); public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; isPrime(10000); // 10000까지의 소수 모두 찾아두기. int n =..

문제https://www.acmicpc.net/problem/4948풀이(17분)import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); boolean flag = true; while(flag){ int testCase = Integer.parseInt(br.readLine()); if(testCase == 0){ br..

에라토스테네스의 체는 소수를 판별해야할 때 매우 유리한 알고리즘이다. 일반적오르 소수를 판별하는 방법은 1을 제외한 자기자신까지를 나눠보며 1과 자기자신으로만 나누어 떨어지는 것이 맞는지 확인하는 방법이다. 하지만 이는 매우 비효율적이다. 그럼 에라토스테네스의 체는 뭘까? 바로 제곱근보다 작은 숫자까지만 확인하면 된다는 것이다. 어떻게 가능할까? 예를 들어 120이라는 숫자가 소수인지 판별해보자. 제곱근은 루트120으로 11^2보다 작다. 즉, 우리는 10까지만 배수들을 지워가며 소수인지 아닌지 판별하면 된다는 것이다. 왜냐하면 10.xxxx * 10.xxxx 가 120이라는 숫자가 된다. 그 말은 120이라는 숫자를 만들기 위해서는 10.xxxx 를 하나는 숫자를 더 크게하고, 하나는 더 낮게 하는 방..