19. 백준 알고리즘 세금, 소수 찾기(에라토스테네스의 체)

츄98 2023. 5. 19. 22:57

18번 백준 알고리즘 문제풀이에 이어서 오늘 푼 나머지 두 문제 해설도 하도록 하자~~

1. 세금 (20492번)

# 백준 세금 문제
# 전체 상금의 22%를 제세공과금으로 납부
# 상금의 20%중 22%를 제세공과금으로 납부

import sys
input = sys.stdin.readline
n = int(input())

money1 = int(n*(0.78))
money2 = int(n*(1-0.2*0.22))

print(money1, money2)

사실 이 문제는 완벽한 수학문제..ㅎㅎ 중고딩 때 가격 문제나 할인 문제와 똑같다..!

사용된 수학 공식 : 금액 x원이 a% 할인된 금액

이를 이용하여 문제의 조건,
# 전체 상금의 22%를 제세공과금으로 납부
# 상금의 20%중 22%를 제세공과금으로 납부

이 두 가지 조건을 잘 만족하도록 하나씩 출력해주면 된다.

2. 소수 찾기 (1978번)

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int,input().split()))
# print(nums) -> [1, 3, 5, 7]
# nums = map(int,input().split()) -> map object

count = 0 
for num in nums:
    error = 0
    if num>1:
        for x in range(2,num):
            if num % x == 0:
                error = 1
        if error == 0:
            count+=1
                
print(count)

풀이 원리는 다음과 같다.
소수는 1과 자기 자신만을 약수로 갖는 수를 말한다. (이때, 1은 소수가 아니다.)

예를 들어 5가 소수인지를 확인하기 위해서는 1을 제외한 5보다 작은 수들을 5와 나누었을 때, 나머지가 0이 되지 않는지를 확인해보면 된다.

5의 경우, 모두 나머지가 0이 되지 않으므로 5는 소수가 된다.

주어진 수들이 소수가 되는지를 판단해주기 위해서
만약 나머지가 0이 되는 경우가 하나라도 있을 시, error라는 변수를 만들어 1을 담았다.
나머지가 모두 0이 되지 않는다면, error의 값은 초기값인 0일 것이고,
error == 0 일 때에 소수의 개수 count를 하나 더하는 것으로 문제를 풀었다.

그렇다면 이 방법 말고, 다른 방법으로 소수 찾기를 해볼 수 없을까?

가장 유명한 풀이방식은 에라토스테네스의 체!!!! 가 있다..!!!

개념을 먼저 살펴보고, 문제풀이에 들어가자..!!

에라토스테네스의 체는 고대 그리스의 수학자인 에라토스테네스가 발견한 소수를 구하는 방법으로 2의 배수, 3의 배수 등을 체처럼 걸러내 소수만 남기는 방법이다.

임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다.
(참고. 시간 복잡도가 O(nlog(logn))이다.)

에라토스테네스의 체의 기본적인 개념은 2의 배수, 3의 배수, 4의 배수, 5의 배수...를 차례대로 제거해 각 사이클마다 지워지지 않은 수 중에서 가장 작은 수를 소수로 채택하는 것이다.

1은 소수가 아니므로 제거
남은 수 중 가장 작은 수가 2이므로 2를 소수로 채택한다.
2와 2의 배수를 제거하고, 남은 수 중 가장 작은 수인 3을 소수로 채택한다.
3과 3의 배수를 제거하고, 남은 수 중 가장 작은 수인 5를 소수로 채택한다.
....

이런 식으로 소수를 찾아나간다.

코드는 다음과 같다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: 0부터 n까지 True 설정(소수로 간주)
    sieve = [True] * n
    sieve[0] = sieve[1] = False # 0과 1은 소수가 아니므로 False로 처리

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] == True:           # i가 소수인 경우 
            for j in range(i*2, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]
    
    # 소수 개수 산출
    print(sieve.count(True))

여기서..! i가 소수일 때 i의 배수를 False로 판정하는 for 문을 살펴보면,
2부터 n까지가 아니라, 2부터 √n까지만 for문을 돌린다. 이러한 이유가 무엇일까?

소수를 찾는 데에 √n까지만 보아도 충분하기 때문이다..!!

예를 들어, 25이하의 소수를 찾는다고 할 때, 2, 3, 5의 소수를 찾고 2의 배수, 3의 배수, 5의 배수를 없앴다고 하자. 이때, √25 = 5 다음 숫자인 6을 보면, 3의 배수이므로 제거가 된 상태이다. 다음 7은 소수이므로 제외되며, 7×2는 2의 배수로 제거되고, 7×3은 3의 배수로 제거가 된 상태이다. 8도 마찬가지로 2의 배수로 제거가 된 상태이다. 이렇게, √n보다 큰 나머지 값들은 이미 제거가 된 상태이다. 따라서 배수를 제거할 때 √n까지만 제거해도 소수만 남게 된다..!!!

자 그럼 이제 에라토스테네스의 체를 이용하여 백준 소수찾기 문제를 풀어보자!!

# 에라토스테네스 체를 이용하여 백준 문제 풀이
sieve = [True]*1000
sieve[0] = sieve[1] = False
for i in range(2, int(1000 ** 0.5) + 1):
    for j in range(i * 2, 1000, i):
        sieve[j] = False

N = int(input())
nums = map(int, input().split())

count = 0

for k in nums:
    if sieve[k]:
        count += 1
print(count)

k가 소수일 경우, sieve[k] 가 True 값을 가질 것이므로 if문을 통과하게 되고, count += 1이 된다.
그렇게 소수의 개수를 셀 수 있다..!!!