일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- nullpointerexception방지
- 자바
- programmers
- 자바리스트정렬
- 백준
- list
- Dependency
- Python
- 자바set
- 리스트
- android
- jetpack
- Kotlin
- filternotnull()
- compose
- Hilt
- 파이썬
- 프로그래머스
- disposableeffect
- 티스토리챌린지
- 백준파이썬
- 자료형
- Java
- 파이썬문법
- 배열
- composelifecycle
- 오블완
- 문자열
- Provider
- ContentProvider
Archives
- Today
- Total
study gomi
[백준/baekjoon] 17103번 골드바흐 파티션 (파이썬) 본문
728x90
반응형
내 제출
- 숫자의 범위가 정해져 있어서 에라토스테네스의 체를 써서 전체 소수를 먼저 구해뒀다.
(에라토스테네스의 체 설명 참고 : https://taetaegom.tistory.com/39)
- 골드바흐의 체 함수 내에서 잘 못 짠 게 있어서 계속 수정을 했다.
- 검사해야 하는 수는 그대로 두고 그 수의 절반 값 까지만 소수 -> 빼도 소수인지 확인하면 되는데 첨에 아무 생각 없이 비교 대상이 되는 소수 리스트 목록을 반으로 자르고 1~검사해야 하는 수를 비교했다. 오잉또잉...ㅋ
- 그 다음에는 바보같이 break를 달아서 검사중인 숫자가 소수가 아니면 그냥 바로 과정이 끝나버리게 했다.
- 여튼... 다시 보니 어려울 게 없는 건데 엄청 헤맸다.
def sieve_of_eratosthenes(num):
primes = [True for _ in range(num + 1)]
p = 2
while p * p <= num:
if primes[p]:
for i in range(p * p, num + 1, p):
primes[i] = False
p += 1
# 1은 소수 아니니까 2부터 마지막 숫자까지 num 까지
return [p for p in range(2, num + 1) if primes[p]]
def goldbach_partition_count(check_n, primes):
count = 0
# ex 36
# 2+34, 3+ 33, 4+ 32, ..., 18 + 18 => 18까지만 확인해 보면 됨.
for check_prime in range(2, check_n // 2 + 1):
# 소수가 아니면 그냥 패스
if not primes[check_prime]:
continue
# 소수인데 원래 숫자에서 뺀 값도 소수인지 확인
if primes[check_n - check_prime]:
count += 1
return count
# 1,000,000 이하의 소수 전부 찾기
max_num = 1000000
all_primes = sieve_of_eratosthenes(max_num)
# 소수 여부를 빠르게 확인하기 위한 리스트
is_prime = [False] * (max_num + 1)
for prime in all_primes:
is_prime[prime] = True
# 테스트 케이스 개수
t = int(input())
for _ in range(t):
n = int(input())
print(goldbach_partition_count(n, is_prime))
결과
- 무려 세 번 틀리고 맞았다.

728x90
반응형
'Practice > Baekjoon' 카테고리의 다른 글
[백준/baekjoon] 28278번 스택2 (파이썬) (1) | 2024.01.12 |
---|---|
[백준/baekjoon] 13909번 창문 닫기 (파이썬) (1) | 2024.01.11 |
[백준/baekjoon] 4134번 다음 소수 (파이썬/자세한 풀이) (2) | 2024.01.10 |
[백준/baekjoon] 2485번 가로수 (파이썬) (1) | 2024.01.10 |
[백준/baekjoon] 1735번 분수 합 (파이썬) (0) | 2024.01.09 |