백준 닷컴 단계 별로 풀어보기 15단계

1단계 최소공배수

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)
첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

import java.io.*;
import java.util.*;

public class Step_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < n; i++) {
			int a=arr[i][0];
			int b=arr[i][1];
			int t=1;
			int count = 2;
			while(true) {
				if(a%count==0&&b%count==0) {
					a/=count;
					b/=count;
					t*=count;
				} else {
					count++;
				}
				if(count>a||count>b||a==1||b==1) {
					break;
				}
			}
			bw.write(a*b*t+"\\n");
		}
		bw.flush();
		bw.close();
	}
}

2차원 int배열에 각 테스트 케이스를 받아준다.
각 배열에 대해 최대 공약수를 구해준다.2부터 시작해서 둘 모두 나눴을 때 나머지가 0이 되는 값들을 누적하여 구한다.
count가 a, b보다 크거나, a, b가 1이 된 경우 더 이상 나눠지지 못하기 때문에 반복문을 종료한다.
최대공약수로 나눠서 나온 a, b와 최대공약수 t를 곱하면 최소 공배수가 된다.

2단계 최소공배수2

한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.
추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

import java.io.*;
import java.util.*;

public class Step_2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long a = Integer.parseInt(st.nextToken());
		long b = Integer.parseInt(st.nextToken());
		long t = Euclidean(a, b);
		long show=a*b/t;
		bw.write(show + "");
		bw.flush();
		bw.close();
	}
	public static long Euclidean(long a, long b) {
	    if (b == 0)
	        return a;
	    return Euclidean(b, a % b);
	}
}

최소공배수는 유클리드 호제법을 이용하여 구할 수 있다.
유클리드 호제법은 a>b일 때 a를 b로 나누고, 다시 b를 a와b의 나머지로 나누어 나머지가 0이 될 때의 b값이 최소공배수가 되는 방식이다.
long으로 하라고 할 때 롱으로 변수지정 하지 않으면 오류가 난다.

3단계 분수 합

한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.
추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

import java.io.*;
import java.util.*;

public class Step_3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());

		int x = a * d + b * c;
		int y = b * d;
		int z = Euclidean(x, y);
		bw.write(x / z + " " + y / z);

		bw.flush();
		bw.close();
	}

	public static int Euclidean(int a, int b) {
		if (b == 0)
			return a;
		return Euclidean(b, a % b);
	}
}

각 분수를 받아준다.
각 분모의 곱을 y, x에는 서로 상대편의 분보*분자의 합을 대입한다.
x,y에 대한 최소공배수를 유클리드 호제법 메소드를 사용하여 구한다
x/z와 y/z의 값을 출력한다.

4단계 가로수

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

import java.io.*;
import java.util.*;

public class Step_3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int gcd = Euclidean(arr[1]-arr[0], arr[2]-arr[1]);
		for (int i=3; i<n; i++) {
			gcd = Euclidean(gcd, arr[i]-arr[i-1]);
		}
		bw.write((arr[n-1]-arr[0])/gcd-(arr.length-1)+"");
		bw.flush();
		bw.close();
	}

	public static int Euclidean(int a, int b) {
		if (b == 0)
			return a;
		return Euclidean(b, a % b);
	}
}

각 좌표의 값을 int 배열에 받아준다.
여러 수의 최대공약수는 최대공약수와 다른 요소와의 연속된 최대공약수 계산으로 구할 수 있다.
첫 gcd로 arr[1]-arr[0]과 arr[2]-arr[1]의 값을 구해주고 arr[3]-arr[2]부터의 연산은 반복문을 통해 작성한다.
총 길이에서 최대공약수를 나눈 값 +1이 전체 가로수의 수이고 거기서 처음 있던 가로수의 수 n을 빼준 값을 출력한다.

5단계 다음 소수

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.
각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

import java.io.*;
import java.math.BigInteger;

public class Step_5 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[] arr = new long[n];
		for(int i=0; i<n; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		br.close();
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for(int i=0; i<n; i++) {
			BigInteger bi = new BigInteger(arr[i]+"");
			bw.write(primeCheck(bi)+"\\n");
		}
		bw.flush();
		bw.close();
	}
	public static BigInteger primeCheck(BigInteger bi) {
		if(bi.isProbablePrime(10)) {
			return bi;
		} else {
			return bi.nextProbablePrime();
		}
	}
}

biginteger 클래스를 이용하여 소수의 체크가 가능하다.
isProbablePrime(정확도)로 소수 여부 체크 가능
nextProbablePrime()으로 다음 소수를 체크 가능하다.

6단계 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Step_6 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		for(int i=n; i<=m; i++) {
			BigInteger bi = new BigInteger(i+"");
			if(bi.isProbablePrime(10)){
				bw.write(i+"\\n");
			}
		}
		bw.flush();
		bw.close();
	}
}

biginteger 클래스를 이용하여 소수를 체크하여 출력한다.

7단계 베르트랑 공준

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

import java.io.*;

public class Step_7 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int[] primeCount = new int[246913];
		boolean[] prime = new boolean[246913];
		
		prime[0]=true;
		prime[1]=true;
		for(int i=2; i<Math.sqrt(prime.length); i++) {
			if(prime[i]) {
				continue;
			}
			for(int j=i*i; j<prime.length; j+=i) {
				prime[j]=true;
			}
		}
		int count =0;
		for(int i=0; i<prime.length; i++) {
			if(!prime[i]) {
				count++;
			}
			primeCount[i]=count;
		}
		
		while(true) {
			int temp = Integer.parseInt(br.readLine());
			if(temp==0) {
				break;
			}
			bw.write(primeCount[2*temp]-primeCount[temp]+"\\n");
		}
		
		
		bw.flush();
		bw.close();
	}
}

소수 여부를 판정하는 boolean 배열과 0~n까지의 소수 개수를 세는 int 배열을 만들어준다.
에라토스테네스의 체를 이용하여 소수는 false, 복합수는 true로 저장하도록 한다.
n에 대해서 소수 여부를 판정할 때 2~루트n까지의 배수 여부를 확인하면 된다. 따라서 2n최대치인 246913의 루트 까지의 수 중 소수를 찾고 찾은 소수의 배수를 2n까지 true로 변환해주면 된다.
0~n까지의 소수 개수를 count를 통해 int배열에 담아준다.
n~2n까지의 배열 소수 개수는 0~2n까지의 소수 개수에서 0~n까지의 소수 개수를 뺀 값이 된다.
각 숫자에 대해 n~2n까지의 소수 개수를 출력한다.

8단계 골드바흐 파티션

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

package stage15;

import java.io.*;
import java.util.*;

public class Step_8 {
	public static void main(String[] args) throws IOException {
		boolean[] prime = new boolean[1000000];
		prime[0] = true;
		prime[1] = true;
		for (int i = 2; i < 1000; i++) {
			if (prime[i]) {
				continue;
			}
			for (int j = i * i; j < 1000000; j += i) {
				prime[j] = true;
			}
		}
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			int temp = Integer.parseInt(br.readLine());
			int count = 0;
			for (int j = 2; j < temp / 2 + 1; j++) {
				if (!prime[j]) {
					if(!prime[temp-j]) {
						count++;
					}
				}
			}
			if (i != n - 1) {
				bw.write(count + "\\n");
			} else {
				bw.write(count + "");
			}
		}

		bw.flush();
		bw.close();
	}
}

에라토스테네스의 체를 이용하여 소수는 false, 복합수는 true로 저장하도록 한다.
각 수를 받아 주고 각 소수에 대해 n-소수가 소수인지 확인하는 반복문을 만든다.
반복문은 각 수를 2로 나눈 값 +1을 기준으로 한다. 수가 소수*2인 경우가 있기 때문
각 수에 대해 세어준 골드바흐 파티션의 수를 출력한다.

9단계 창문 닫기

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.
마지막에 열려 있는 창문의 개수를 출력한다.

import java.io.*;
import java.util.*;

public class Step_9 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int count = 0;
		for(int i=1; i*i<=n; i++) {
			count++;
		}
		bw.write(count+"");
		bw.flush();
		bw.close();
	}
}

창문이 열려있기 위해서는 약수의 개수가 홀수여야 한다.
약수의 개수가 홀수인 수는 완전제곱수이다.
반복문을 만들어 i제곱이 n보다 작을 경우의 완전제곱수의 수를 세고 출력한다.

'백준' 카테고리의 다른 글

백준 닷컴 단계 별로 풀어보기 19단계 (1)	2023.10.23
백준 닷컴 단계 별로 풀어보기 16단계 (1)	2023.10.22
백준 닷컴 단계 별로 풀어보기 14단계 (1)	2023.10.11
백준 닷컴 단계 별로 풀어보기 13단계 (1)	2023.10.09
백준 닷컴 단계 별로 풀어보기 12단계 (1)	2023.10.08

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

개발자 지망생의 공부일지

백준 닷컴 단계 별로 풀어보기 15단계

'백준' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

백준 닷컴 단계 별로 풀어보기 15단계

'백준' 카테고리의 다른 글

'백준' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역