ING

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 베르트랑 공준 ( 문제 번호 : 4948 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

1) JAVA

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 cnt = 0;
			if(n==0) break;
			
			for(int i=n+1; i<=2*n; i++){
				int result = 0;
				int half = (int)Math.sqrt(i);
				if(i==1) result++;

				for(int j=2; j<=half; j++){
					if(i%j==0){
						result++;
						break;
					}
				}
				
				if(result==0){
					cnt++;
				}
			}
			System.out.println(cnt);
		}
		scan.close();
	}

}

2) PYTHON

   * 파이썬은 자바처럼 해결하게 될 경우 시간 초과가 뜨게 된다.

     따라서 2n의 범위까지 나오는 소수들을 미리 구한 뒤 소수의 개수를 더해주는게 시간을 줄일 수 있다.

     반복해서 사용하게 될 경우 그때 그때 다시 계산해줄 필요가 없으므로 자바 또한 이러한 방식으로 바꿔서 풀면

     좋을 것 같다

import math
k = 123456*2+1
num_list = [1]*k
for i in range(1, k):
    if i == 1:
        continue
    for k in range(2, int(math.sqrt(i))+1):
        if i % k == 0:
            num_list[i] = 0
            break

while True:
    n = int(input())
    sum = 0
    if n == 0:
        break
    for i in range(n+1, 2*n+1):
        sum += num_list[i]
    print(sum)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 소수 구하기 ( 문제 번호 : 1929 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

1) JAVA

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();
		
		for(int i=m; i<=n; i++){
			int result = 0;
			int x = (int)Math.sqrt(i);
			if(i==1) result++;

			for(int j=2; j<=x; j++){
				if(i%j==0){
					result++;
					break;
				}
			}
			
			if(result==0){
				System.out.println(i);
			}
		}
	}

}

2) PYTHON

import math
m, n = map(int, input().split())
for i in range(m, n+1):
    result = 0
    if i == 1:
        result += 1
        continue
    x = int(math.sqrt(i))
    for k in range(2, x+1):
        if i % k == 0:
            result += 1
            break

    if result == 0:
        print(i)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 소수 ( 문제 번호 : 2581 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int m = Integer.parseInt(scan.nextLine());
		int n = Integer.parseInt(scan.nextLine());
		int sum = 0;
		int min = n;
		for(int i=m; i<=n; i++){
			int result = 0;
			if(i==1) result++;

			for(int j=2; j<i; j++){
				if(i%j==0){
					result++;
					break;
				}
			}
			
			if(result==0){
				sum += i;
				if(min>i){
					min = i;
				}
			}
		}
		
		if(sum==0){
			System.out.println(-1);
		}else{
			System.out.println(sum);
			System.out.println(min);	
		}
		scan.close();
	}

}

2) PYTHON

m = int(input())
n = int(input())
sum = 0
min = n
for i in range(m, n+1):
    result = 0
    if i == 1:
        result += 1
        continue

    for k in range(2, i):
        if i % k == 0:
            result += 1
            break

    if result == 0:
        sum += i
        if min > i:
            min = i

if sum == 0:
    print(-1)
else:
    print(sum)
    print(min)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 소수 찾기 ( 문제 번호 : 1978 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = Integer.parseInt(scan.nextLine());
		int result = n;
		for(int i=0; i<n; i++){
			int temp = scan.nextInt();
			if(temp==1) result--;
			for(int j=2;j<temp;j++){
				if(temp%j==0){
					result--;
					break;
				}
			}
		}
		System.out.println(result);
		scan.close();
	}

}

2) PYTHON

n = int(input())
num_list = map(int, input().split())
result = n
for i in num_list:
    if i == 1:
        result -= 1
        continue

    for k in range(2, i):
        if i % k == 0:
            result -= 1
            break
print(result)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학1 중 Fly me to the Alpha Centauri ( 문제 번호 : 1011 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

[ 거리의 제곱근 루트 패턴 ]

- 정수일 경우

   ex ) 0~1, 0~4, 0~9

   공식 -> 2*제곱근의 루트 -1

- 반올림할 경우

      - 버림 

             ex ) 0~2, 0~5, 0~6

             공식 -> 2*제곱근의 루트 절대값 -1

      - 올림

             ex ) 0~3, 0~7, 0~8

             공식 -> 2*제곱근의 루트 절대값

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int t = Integer.parseInt(scan.nextLine());

		for(int i=0; i<t; i++){
			long x = scan.nextLong();
			long y = scan.nextLong();
			long distance = y-x;
			long max = (int)Math.sqrt(distance);

			//0~1, 0~4, 0~9
			if(max == Math.sqrt(distance)){
				System.out.println(2*max-1);
			//0~2,0~5, 0~6	
			}else if( Math.sqrt(distance) - max <= 0.5 ){
				System.out.println(2*max);
			//0~3, 0~7, 0~8
			}else{
				System.out.println(2*max+1);
			}
		}
		scan.close();
	}
}

2) PYTHON

import math

t = int(input())
for _ in range(t):
    x, y = map(int, input().split())
    distance = y - x
    max = int(math.sqrt(distance))
    if max == math.sqrt(distance):
        print(2*max-1)
    elif math.sqrt(distance) - max <= 0.5:
        print(2*max)
    else:
        print(2*max+1)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학1 중 ACM 호텔 ( 문제 번호 : 10250 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

1) JAVA

import java.util.Scanner;

public class backJoon_10250 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		//테스트 개수 
		int t = Integer.parseInt(scan.nextLine());
		for(int i=0; i<t; i++){
			String[] data = scan.nextLine().split(" ");
			int h = Integer.parseInt(data[0]); // 층 수
			int w = Integer.parseInt(data[1]); // 방 수
			int n = Integer.parseInt(data[2]); // 몇번째 손님
			
			int floor = 0;
			int room = 0;
			int cnt = 0;
			
			for(int j=1;j<=w;j++){
				if(cnt==n) break;
				room++;
				for(int k=1; k<=h;k++){
					if(cnt==n) break;
					cnt ++;
					floor=k;
					
				}
			}

			String result = floor + (room<10 ? "0":"") + room;
			System.out.println(result);

		}
		scan.close();

	}

}

2) PYTHON

t = int(input())
for _ in range(t):
    h, w, n = map(int, input().split())
    cnt = 0
    room = 0
    floor = 0
    for i in range(1, w+1):
        if cnt == n:
            break
        room = i
        for j in range(1, h+1):
            if cnt == n:
                break
            cnt += 1
            floor = j
    room = format(room, '02')
    print('%s%s' % (floor, room))

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학1 중 부녀회장이 될테야 ( 문제 번호 : 2775 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

공통적으로 0층은 n(호) 마다 추가되고,

그 외의 층들의 인원 수는 예를 들어 302호면 202호+301호 값이 더해지면 된다는 공식을 세울 수 있다.

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt(); //test case

		int [][] apartment = new int[15][15];
		
		//초기값 설정
		for(int i=0;i<=14;i++){
			apartment[i][1] = 1;
			apartment[0][i] = i;
		}

		//초기값 이외의 설정
		for(int i=0;i<t;i++){
			int k = scan.nextInt(); //층
			int n = scan.nextInt(); //호
			
			for(int j=1; j<=k; j++){//층만큼 뺑뺑이
				for(int p=2; p<n+1;p++){
					apartment[j][p] = apartment[j-1][p]+apartment[j][p-1];
				}
			}
			System.out.println(apartment[k][n]);
		}
		scan.close();
	}
}

2) PYTHON

t = int(input())
for _ in range(t):
    k = int(input())
    n = int(input())

    apartment = [i for i in range(1, n+1)]
    for _ in range(k):
        for j in range(1, n):
            apartment[j] += apartment[j-1]
    print(apartment[n-1])

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학1 중 벌집 ( 문제 번호 : 2292 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

[1번 줄]

1

[2번 줄]

2~7 -> 6

[3번 줄]

8~19 -> 12

[4번 줄]

20~37 -> 18

줄(=> 몇번 지나가야 있는지 알수있는 숫자)을 보면 6씩 증가합니다.

적어도 줄의 마지막 숫자안에 들어가 있으면 해당 줄의 수만큼만 지나면 되어

줄의 숫자를 구한다는 생각으로 해보았습니다.

1) JAVA

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();
		
		int row=1;
		int last_num=1;
		while(true){
			if(last_num>=n) break;
			last_num+=6*row;
			row++;
		}
			System.out.println(row);
	}
}

2) PYTHON

n = int(input())
row = 1
max_num = 1

while True:
    if max_num >= n:
        print(row)
        break
    max_num += 6*row
    row += 1

여러분도 한번 풀어보세요!