CS/Baekjoon

[Algorithm] 백준 단계별로 풀어보기 - 단계 9. 수학(2)

칸타탓 2019. 7. 10. 17:48

소수, 기하 다루기

1978. 소수 찾기

* 소수: 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수

=> 1과 자기 자신만을 약수로 갖는 자연수

ex) 2, 3, 5, 7, 11 ...

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_1978 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(rd.readLine());
		String[] input = rd.readLine().split(" ");
		int cnt, cnt2 = 0, tmp;
		
		for(int n=0; n<N; n++) {
			tmp = Integer.parseInt(input[n]);
			cnt = 0;
			for(int i=1; i<=tmp; i++) {
				if(tmp%i==0) cnt++;
				if(cnt>2) break;
			}
			if(cnt==2) cnt2++;
		}
		System.out.println(cnt2);
	}
}

약수가 2개 이하일 때만 카운팅

 

2581. 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class BOJ_2581 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(rd.readLine());
		int N = Integer.parseInt(rd.readLine());
		rd.close();

        ArrayList<Integer> sosu = new ArrayList<Integer>();
        int cnt, sum=0;
        
        for(int i=M; i<=N; i++) {
        	cnt = 0;
        	for(int j=1; j<=i; j++) {
        		if(i%j==0) cnt++;
        		if(cnt>2) break;
        	}
        	if(cnt==2) sosu.add(i);
        }
        
        int size = sosu.size();
        if(size > 0) {
	        for(int i=0; i<size; i++) 
	            sum += sosu.get(i);
	        System.out.println(sum);
	        System.out.println(sosu.get(0));
        } else
        	System.out.println("-1");
	}
}

 

1929. 소수 구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. (1 ≤ M ≤ N ≤ 1,000,000)
* 기존 방법 사용하면 시간 초과 -> 에라토스테네스의 체 이용하여 풀기!

 

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
  2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  9. 자기 자신을 제외한 7의 배수를 모두 지운다. (...반복)
  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11*11 > 120이므로 11보다 작은 수의 배수들만 지운다.

문제의 경우, 1,000,000이므로 sqrt(N)보다 작은 수의 배수들만 지운다.

package algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_1929 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		String[] input = rd.readLine().split(" ");
		int M = Integer.parseInt(input[0]);
		int N = Integer.parseInt(input[1]);
		rd.close();
		
		boolean[] arr = new boolean[1000001];
		Arrays.fill(arr, true);
		//0과 1 소수 아님 -> 미리 초기화
		arr[0] = false;
		arr[1] = false;

		//이미 배수로 걸러진 수는 false
		//나중에 true(소수)일 때만 출력
		for(int i=2; i<=(int)Math.sqrt(N); i++) {
			if(arr[i]) {
				//i+i: 자신은 포함되면 안되기 때문
				//j+=i: 배수 만들기
				for(int j=i+i; j<=N; j+=i) {
					arr[j] = false;
				}
			}
		}
		
		for(int k=M; k<=N; k++) {
			if(arr[k])
				System.out.println(k);
		}
	}
}

 

4948. 베르트랑 공준

n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. (n ≤ 123456)

에라토스테네스의 체를 사용해서 풀었다.

 

boolean[] arr = new boolean[n2+1]로 배열 선언을 while문 안에 넣었더니 런타임 에러가 떠서 배열 크기 123456*2+1로 수정!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_4948 {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		boolean[] arr = new boolean[246913];
		arr[0] = arr[1] = false;
		
		while(true) {
			int n = Integer.parseInt(rd.readLine());
			if(n==0) break;
			int n2 = 2*n;
			Arrays.fill(arr, true);

			int sqrt = (int)Math.sqrt(n2);
			for(int i=2; i<=sqrt; i++) {
				if(arr[i]) {
					for(int j=i+i; j<=n2; j+=i) {
						arr[j] = false;
					}
				}
			}
			
			int sum = 0;
			for(int k=n+1; k<=n2; k++) {
				if(arr[k])
					sum++;
			}
			System.out.println(sum);
		}
	}
}

 

아래와 같은 경우에 런타임 에러가 발생한다고 한다.

  1. 배열에 할당된 크기를 넘어서 접근했을 때

  2. 전역 배열의 크기가 메모리 제한을 초과할 때

  3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때

  4. 0으로 나눌 떄

  5. 라이브러리에서 예외를 발생시켰을 때

  6. 재귀 호출이 너무 깊어질 때

  7. 이미 해제된 메모리를 또 참조할 때

9020. 골드바흐의 추측

소수 응용 문제

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. (4 ≤ n ≤ 10,000)

package algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_9020 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(rd.readLine());
		
		boolean[] arr = new boolean[10001];
		Arrays.fill(arr, true);
		arr[0] = arr[1] = false;
		
		//소수 구하기
		for(int i=2; i<=100; i++) {
			for(int j=i+i; j<=10000; j+=i) {
				arr[j] = false;
			}
		}
		
		for(int t=0; t<T; t++) {
			int n = Integer.parseInt(rd.readLine());
			int x = 0, y = 0;

			//골드바흐 파티션 찾기
			for(int k=n-1; k>=n/2; k--) {
				if(arr[k]) {
					for(int l=2; ; l++) {
						if(arr[l]) {
							if(k+l == n) {
								x = k; y = l; break;
							}
							if(k+l > n) break;
						}
					}
				}
			}
			System.out.println(y+" "+x);
		}
	}
}

소수 찾아서 배열 만들고, 입력받은 수/2 만큼 배열 반복문 2개 돌면서 차이가 가장 작은 두 소수를 출력하도록 풀었는데 시간초과 발생

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_9020 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(rd.readLine());
		
		boolean[] arr = new boolean[5082];
		Arrays.fill(arr, true);
		arr[0] = arr[1] = false;
		//소수
		for(int i=2; i<=72; i++) {
			for(int j=i+i; j<=5081; j+=i) {
				arr[j] = false;
			}
		}
		//골드바흐 파티션
		for(int t=0; t<T; t++) {
			int n = Integer.parseInt(rd.readLine());
			int left = n/2, right = n/2;
			
			while(true) {
				if(arr[left] && arr[right])
					break;
				left--; right++;
			}
			System.out.println(left+" "+right);
		}
	}
}

에라토스테네스의 체로 소수를 찾고, 입력받은 수를 반으로 나눈 다음 왼쪽의 수는 --, 오른쪽의 수는 ++ 한다.

배열에서 동시에 소수가 나오면 출력하고 종료!

 

1085. 직사각형에서 탈출

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class BOJ_1085 {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = reader.readLine().split(" ");
		int x = Integer.parseInt(input[0]);
        int y = Integer.parseInt(input[1]);
        int w = Integer.parseInt(input[2]);
        int h = Integer.parseInt(input[3]);
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        list.add(x);
        list.add(y);
        list.add(w - x);
        list.add(h - y);
        
        Collections.sort(list);
        System.out.println(list.get(0));
	}
}

상, 하, 좌, 우를 모두 고려하기!

 

3009. 네 번째 점

package algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_3009 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		
		int listX[] = new int[3];
		int listY[] = new int[3];
		
		String[] input1 = rd.readLine().split(" ");
		listX[0] = Integer.parseInt(input1[0]);
		listY[0] = Integer.parseInt(input1[1]);
		
		String[] input2 = rd.readLine().split(" ");
		listX[1] = Integer.parseInt(input2[0]);
		listY[1] = Integer.parseInt(input2[1]);
		
		String[] input3 = rd.readLine().split(" ");
		listX[2] = Integer.parseInt(input3[0]);
		listY[2] = Integer.parseInt(input3[1]);
		
		int newX = findNumber(listX);
		int newY = findNumber(listY);
		
		System.out.println(newX+" "+newY);
	}
	
	private static int findNumber(int[] list) {
		for(int i=0; i<2; i++) {
			for(int j=i+1; j<=2; j++) {
				if(list[i] == list[j]) {
					list[i] = list[j] = -1; break;
				}
			}
		}
		int res = 0;
		for(int i=0; i<3; i++) {
			if(list[i] > 0)
				res = list[i];
		}
		
		return res;
	}
}

X 배열 만들고, Y 배열 만들어서 각각 값을 넣어주고, 각각의 배열에서 중복수를 제거해준 후 출력하면 됨

 

4153. 직각삼각형

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BOJ_4153 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		
		List<Integer> list = new ArrayList<Integer>();
		int a, b, c;
		
		while(true) {
			String[] input = rd.readLine().split(" ");
			list.add(Integer.parseInt(input[0]));
			list.add(Integer.parseInt(input[1]));
			list.add(Integer.parseInt(input[2]));
			
			if(list.get(0) == 0)
				break;
			
			Collections.sort(list);
			a = list.get(0);
			b = list.get(1);
			c = list.get(2);
			
			//직각삼각형 확인 - c = √a^2+b^2
			int sum = (int)Math.pow(a, 2) + (int)Math.pow(b, 2);
			int res = (int)Math.sqrt(sum);
			
			if(c == res) System.out.println("right");
			else System.out.println("wrong");
			
			list.clear();
		}
	}
}

입력받은 수를 배열에 넣고, 가장 큰 수를 c, 작은 수 두 개를 a, b로 놓는다.

피타고라스의 정리를 통해서 푼 문제.

 

3053. 택시 기하학

* 택시 기하학

택시 기하학에서의 원

정사각형 대각선의 길이 = 2R이라고 했을 때, 피타고라스의 정리에 의해 2R^2 = 1a^2 + 1a^2가 된다.

(a는 정사각형 한 변의 길이)

이를 정리하면 2R^2 = 2a^2이다.

 

택시 기하학에서의 원은 정사각형이다. 정사각형의 넓이는 가로*세로임.

따라서 2R*2가 택시 기하학에서의 원의 넓이에 해당한다.

 

그리고,  정답과의 오차는 0.0001까지 허용한다. 라는 조건이 주어진다. 이에 주의하여 출력하기!

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_3053 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		double R = Integer.parseInt(rd.readLine());
		
		System.out.println(String.format("%6f", Math.PI*(R*R)));
		System.out.println(String.format("%6f", 2*R*R));
	}
}

 

1002. 터렛

참고: https://mathbang.net/101

조건: r1<=r2

(1) 두 점에서 만나는 경우

r2 - r1 < d < r1 + r2

(2) 한 점에서 만나는 경우

r1 + r2 = d

r2 - r1 = d

(3) 만나지 않는 경우

r1 + r2 < d

r2 - r1 > d

x1=x2 && y1=y2(두 좌표가 같은 경우) && r1 != r2

(4) 무한대가 출력되는 경우 = 두 원이 완전히 겹치는 경우

x1=x2 && y1=y2(두 좌표가 같은 경우) && r1 = r2

 

 

* 원 중심간의 거리

d는 피타고라스의 정리에 의해 구한다

 

x, y를 좌표로 갖는 점과 마린이 있는 위치 r을 입력받는다. 이를 원으로 나타낼 수 있다.

피타고라스의 정리와 두 원의 위치관계를 이용하여 푸는 문제이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_1002 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(rd.readLine());
		
		for(int i=0; i<T; i++) {
			String[] input = rd.readLine().split(" ");
			int x1 = Integer.parseInt(input[0]);
			int y1 = Integer.parseInt(input[1]);
			int r1 = Integer.parseInt(input[2]);
			int x2 = Integer.parseInt(input[3]);
			int y2 = Integer.parseInt(input[4]);
			int r2 = Integer.parseInt(input[5]);
			
			int rpr = r1+r2;
			int rmr = Math.abs(r1-r2);
			double d = Math.sqrt(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));

			if(x1==x2 && y1==y2) {
				if(r1==r2) System.out.println("-1");
				if(r1!=r2) System.out.println("0");
			} else {
				if(d==rpr || d==rmr) System.out.println("1");
				if(d<rpr && d>rmr) System.out.println("2");
				if(d>rpr || d<rmr) System.out.println("0");
			}
		}
	}
}

 

저작자표시 비영리 변경금지

'CS > Baekjoon' 카테고리의 다른 글

[Algorithm] 백준 단계별로 풀어보기 - 단계 11. 정렬  (0) 2019.07.30
[Algorithm] 백준 단계별로 풀어보기 - 단계 10. 브루트 포스  (0) 2019.07.30
[Algorithm] 백준 단계별로 풀어보기 - 단계 8. 규칙 찾기 (2)  (0) 2019.06.28
[Algorithm] 백준 단계별로 풀어보기 - 단계 8. 규칙 찾기 (1)  (0) 2019.04.18
[Algorithm] 백준 단계별로 풀어보기 - 단계 7. 문자열  (0) 2019.04.17

'CS/Baekjoon'의 다른글

  • 현재글[Algorithm] 백준 단계별로 풀어보기 - 단계 9. 수학(2)
댓글

티스토리툴바