[백준] 9단계 문제 모음

1

1978

소수 찾기

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		int count = 0;
		for(int t = 0; t<T; t++) {
			int n = scan.nextInt();
			if(n==1) continue;
			else if(n==2) count++;
			else {
				for(int i=2; i<n; i++) {
					if(n%i == 0) break;
					if(i == n-1) count++;
				}	
			}
		}
		System.out.println(count);
		scan.close();
		
	}

}

---

2

2581

소수

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int M = scan.nextInt();
	int N = scan.nextInt();
	scan.close();
	int array[] = new int[N-M+1];
	int count = 0;
	int sum = 0;

	
	if(M==1 && N ==1);
	else if((M==2 || M ==1) && N==2) {
		array[0] = 2;
		count++;
	}
	else {
		for(int i =M; i<= N; i++) {
			if(i==1) continue;
			else if (i==2) {
				array[count] = 2;
				count++;
				continue;
			}
			for(int j=2; j<i; j++) {
				if(i%j ==0 ) break;
				if(i ==j+1) {
					array[count] = i;
					count++;
				}
			}
			
		}
	}
	if(count == 0) System.out.println(-1);
	else {
		for(int i =0; i<array.length; i++) {
			sum += array[i];
		}
		System.out.println(sum);
		System.out.println(array[0]);

		}
	}

}

---

3

11653

소인수분해

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		scan.close();
		if(N == 1 );
		else if(N==2) System.out.println(2);
		else {
			for(int i=2; i<N; i++) {
				if(N%i == 0) {
					System.out.println(i);
					N = N/i;
					i = 1;
					if(N==1) break;
				}
				if(i == N-1) System.out.println(N);
			}
		}

	}

}

---

4

1929

소수 구하기

처음에 문제풀 때 에라토스테네스의 체로 풀어보라는 말을 못보고 내 식대로 했다가 시간초과가 났다.

아래코드는 시간초과 코드이다. 

import java.io.*;
import java.util.StringTokenizer;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sbf = new StringTokenizer(bfr.readLine(), " ");
		int M =Integer.parseInt(sbf.nextToken());
		int N =Integer.parseInt(sbf.nextToken());
		for(int i = M; i<=N; i++) {
			for(int j = 2; j<i; j++) {
				if(i%j== 0) break;
				if(i==j+1) System.out.println(i);
			}
		}
	}

}

그래서 에라토스테네스의 체를 검색해보니

 예전에 중고등학생 때 봤었던 소수 구하는 방법이 에라토스테네스의 체라는 것이였다. 위키백과에 이 방법을 구현한 코드가 있어서 코드분석을 하고 알고리즘을 가져다 사용하였다.

import java.util.Scanner;

public class Main {
	public static boolean array[];
	
	public static void Eratos() {
		array[0] = array[1] = true;
		
		for(int i = 2; i <= Math.sqrt(array.length); i++) { //제곱근
			if(array[i] == true) continue; 
			for(int j = i * i; j < array.length; j += i) {
				array[j] = true;
			}
		}
	}
	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int M = scan.nextInt();
		int N = scan.nextInt();
		scan.close();
		
		array = new boolean[N+1]; // default = false
		Eratos();
		for(int i = M; i<=N; i++) {
			if(array[i] == false) System.out.println(i);
		}
	}
	
}

 

---

5

4948

베르트랑 공준

처음에는 아래와 같이 했는데 시간초과가 나고, 직접 제일 큰 수를 넣어보니 눈으로 확인할 수 있을정도의 속도로 많이 느렸다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		while (true) {
			int n = scan.nextInt();
			int count = 0;
			if(n == 0) return;
			if(n == 1) {
				System.out.println(1);
				continue;
			}
			
			for(int i = n+1; i<=2*n; i++) {
				for(int j =2; j<i; j++) {
					if(i%j == 0 ) break;
					if(j == i-1) count++;
				}
			}
			System.out.println(count);
		}
	}

}

 그래서 바로 직전의 문제를 가져와서 코드를 다시 짰다. 확실히 속도 차이가 느껴졌다.

import java.util.Scanner;

public class Main {
	public static boolean array[];
	
	public static void Eratos() {
		array[0] = array[1] = true;
		
		for(int i = 2; i <= Math.sqrt(array.length); i++) { //제곱근
			if(array[i] == true) continue; 
			for(int j = i * i; j < array.length; j += i) {
				array[j] = true;
			}
		}
	}
	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true) {
			int N = scan.nextInt();
			if(N==0) return;		
		array = new boolean[2*N+1]; // default = false
		Eratos();
		int count = 0;
		for(int i = N+1; i<=2*N; i++) 
			if(array[i] == false) count++;
		System.out.println(count);
		}
	}
	
}

---

6

9020

골드바흐의 추측

import java.util.Scanner;

public class Main {
public static boolean array[];
	
	public static void Eratos() {
		array[0] = array[1] = true;
		
		for(int i = 2; i <= Math.sqrt(array.length); i++) { //제곱근
			if(array[i] == true) continue; 
			for(int j = i * i; j < array.length; j += i) {
				array[j] = true;
			}
		}
	}
	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int t = 0; t<T; t++) {
			int N = scan.nextInt();	
			array = new boolean[10000]; // default = false
			Eratos();

			for(int i = 0; i<(N/2); i++) {
				if(!array[N/2 - i] && !array[N/2 + i]) {
					System.out.println((N/2 -i) + " " + (N/2 +i));
					break;
				}
		}
		
		}
	}
	
}

---

7

1085

직사각형에서 탈출

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int N[] = new int[4];
		for(int i = 0; i<N.length; i++)
			N[i] = scan.nextInt();
		
		N[2] -= N[0];
		N[3] -= N[1];
		
		int min = N[0];
		
		for(int i=1; i<4; i++) 
			if(min>N[i])
				min = N[i];
		
		System.out.println(min);
		
	}

}

---

8

3009

네 번째 점

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int ax = scan.nextInt();
		int ay = scan.nextInt();
		int bx = scan.nextInt();
		int by = scan.nextInt();
		int cx = scan.nextInt();
		int cy = scan.nextInt();
	
		int x = 0 , y = 0;

		if(ax == bx) x= cx;
		else if(ax == cx) x= bx;
		else x= ax;
		
		if(ay == by) y =cy;
		else if(ay == cy) y = by;
		else y = ay;
		
		System.out.println(x + " " + y);
	
	}

	
}

---

9

4153

직각삼각형

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			
			if(a==0 && b==0 &&c==0) return;
			
			int max =0;
			if(a>b && a>c)
				if(a*a == b*b + c*c) System.out.println("right");
				else System.out.println("wrong");
			
			else if(b>a && b>c)
				if(b*b == a*a + c*c) System.out.println("right");
				else System.out.println("wrong");
			
			else
				if(c*c == a*a + b*b) System.out.println("right");
				else System.out.println("wrong");
		}

	}

}

---

10

3053

택시 기하학

택시 기하학이 무엇이냐.

import java.math.*;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		double R = scan.nextDouble();
        scan.close();
		System.out.println(R * R * Math.PI);
		System.out.println(2 * R * R);
	}

}

---

11

1002

터렛

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int i = 0; i<T; i++) {
			int x1 = scan.nextInt();
			int y1 = scan.nextInt();
			int r1 = scan.nextInt();
			int x2 = scan.nextInt();
			int y2 = scan.nextInt();
			int r2 = scan.nextInt();
			
			if(x1 == x2 && y1 == y2) {// 두 점의 좌표가 같으면
				if(r1 != r2) {//접점없음
					System.out.println(0); 
					continue;
				}
				else { //접점 무한대
					System.out.println(-1);
					continue;
				}
			}
			else {
				double dis = Math.sqrt(Math.pow(x2-x1, 2) + Math.pow(y2-y1,2));
			
				if(dis > r1 + r2 || dis <Math.abs(r1-r2)) System.out.println(0);
			
				else if(dis == r1+r2 || dis == Math.abs(r1-r2)) System.out.println(1);
			
				else System.out.println(2);
			}
		}
		scan.close();

	}

}