일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 알고리즘
- web
- react
- C++
- error
- 분할메모리할당
- CPU 스케줄링
- Java
- 토이프로젝트
- 타입스크립트
- 파이썬
- 프로그래머스
- 협업
- codeup
- 스프링
- 기초100제
- OS
- js to ts
- 일상
- Spring
- Redux
- 정렬
- 백준
- 코드업
- react-redux
- 자료구조
- 공부
- Operating System
- 리덕스장바구니
- memory
- Today
- Total
감자튀김 공장🍟
[백준/9020] 골드바흐의 추측 (with 파이썬) 본문
✔ 문제
✔ 풀이
🤢 풀다가 포기한 코드
t = int(input())
nums = []
for i in range(2, 10000):
for j in range(2, int(i ** 0.5) + 1):
if i % j == 0:
break
else:
nums.append(i)
for _ in range(t):
n = int(input())
sums = []
mins = []
for i in nums:
for j in nums:
if i + j == n:
sums.append([i, j])
break
# 미완
코드가 점점 더 길어지고... 위에서 더 필요한 코드는
1. 예를 들어 n이 8일 때 [3, 5] [5, 3]이 저장되는데 이를 [3, 5] 하나만 저장되게 하는 코드
2. 만약 1번을 수정하지 않았을 때 sums에 저장된 i, j의 가장 작은 차이를 구하기 위해 mins 함수에 i - j 값을 저장하는 코드
3. 2번 수행했을 경우 가장 작은 차이의 값의 인덱스를 구해 출력하게 해야하지만 min()을 사용할 경우 음수가 답으로 출력될 수 있기 때문에 이를 방지하는 코드
등등... 이 필요하다... 풀다보니까 이게 아닌 것 같아서 노선 변경.. 🥺
🙇♀️ 답안 코드
def is_Prime(n):
if n == 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
t = int(input())
for _ in range(t):
n = int(input())
a, b = n // 2, n // 2
while a > 0:
if is_Prime(a) and is_Prime(b):
print(a, b)
break
else:
a -= 1
b += 1
✔ 설명
1. 소수를 미리 구해놓는 것이 아니라 해당 숫자가 소수인지 판별하는 함수를 미리 구현한다. (def is_Prime)
2. n을 입력 받아서 n // 2 값을 a, b로 나눠 저장한다.
ㄴ 가장 작은 차의 소수를 구할거면 n // 2를 한 값으로 구하는 것이 다른 판별 코드 없이 제일 빠르다.
3. a는 -1씩, b는 +1 씩 해 a, b 둘 다 소수인 값을 구하면 된다.
ㄴ n을 2로 나눈 후 a, b를 동시에 -1, +1 하므로 a+b의 값은 계속 n이 나온다.
✔ 후기
처음에 짜던 코드로 계속 했으면 분명히 시간 초과가 났을 것이다...
계속 풀다가 for문의 연속이길래 이게 아닌 것 같아서 멈췄다..
그리고 다른 방법이 도저히 생각이 안나서 구글링 해봤더니 다른 방법들이 많이 있었다..
n // 2를 하면 따로 if a + b == n: 이라는 조건을 쓰지 않아도 된다는 점이 정말... 머리의 전구가 딱! 켜지는 순간이었다.😥
'Algorithm > BOJ' 카테고리의 다른 글
[백준/2566] 최댓값 (with 파이썬) (0) | 2022.11.04 |
---|---|
[백준/2738] 행렬 덧셈 (with 파이썬) (0) | 2022.11.03 |
[백준/4948] 베르트랑 공준 (with 파이썬) (0) | 2022.11.01 |
[백준/1929] 소수 구하기 (with 파이썬) (0) | 2022.10.31 |
[백준/11653] 소인수분해 (with 파이썬) (0) | 2022.10.30 |