본문 바로가기

알고리즘/백준

 (87)
[문제]백준 9020번 골드바흐의 추측 * 출처: 백준 단계별로 풀어보기 기본 수학2 www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 소수 문제! 우선 에레토스테네스의 체를 이용해 prime 배열을 초기화 시켜준다. 이후, 두 소수의 합이 n이 되는 쌍을 찾으면 되는 것이다. n = first + second라고 할 때, 여기서 n을 절반으로 나눈 다음, first는 n/2에서 하나씩 줄여가고, second는 n/2에서 하나씩 증가시키면서 찾아가면 된다. import java...
[문제] 백준 4948번 베트르랑 공준 - 소수 * 출처: 백준 단계별로 풀어보기 기본수학2 www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 에스트라테네스의 체를 이용해 문제를 풀었다. 여기서 주의할 점은 반복문 돌릴 때 인덱스 범위이다. i*i를 할 때 MAX_NUM을 넘어가면 안되고, 2*n할 떄도 마찬가지로 MAX_NUM을 넘어가면 안된다! 이부분만 주의하면 나머지는 앞선 소수 찾기 문제와 동일하다. import java.io.*; import java.util.StringTokenizer; ..
[문제] 백준 1929번 소수 구하기 - 에라토스테네스의 체 이용하기 * 출처: 백준 단계별로 풀어보기 기본 수학 2 www.acmicpc.net/problem/1929 [ 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ](https://www.acmicpc.net/problem/1929) import java.io.*; import java.util.StringTokenizer; public class Main { public static boolean[] prime; public static void main(String[] args) throws IOException { BufferedReader in..
[문제] 백준 11653번 소인수분해 * 출처: 백준 단계별로 풀어보기 기본수학 2 www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader in = new BufferedReader(new ..
[문제] 백준 2581번 소수 * 출처: 백준 단계별로 풀어보기: 기본수학2 www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatExcept..
[문제] 백준 2775번 부녀회장이 될테야 * 출처: 백준 단계별로 풀어보기: 기본 수학1편 https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int flat[][] = new int[15][14]; public static void main(String[]..
[문제] 백준 2839번 설탕 배달 www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 1. 첫번쨰 풀이 5의 배수를 기준으로 잘라서 나열해보자. 첫 행은 무게고, 아래 순서쌍은 (3kg 봉지 개수, 5kg 봉지 개수)이다. 3 4 5 (1,0) X (0, 1) 6 7 8 9 10 11 12 13 14 15 (2,0) -> 2 X (1,1)-> 2 (3,0)-> 3 (0,2)->2 (2,1)->3 (4,0)->4 (1,2)->3 (3,1)->4 (0,3) ->3 16 17 18 19 20 21 22 2..
[문제] 백준 10757번 큰 수 A+B * 출처: 백준 단계별로 풀어보기 기본수학 1편 www.acmicpc.net/problem/10757 [ 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net ](https://www.acmicpc.net/problem/10757) long으로 풀면 되는게 아니라, 문자열에 저장해서 풀어야 하는 문제다. (배열로도 가능) import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next(); Strin..

티스토리툴바