공부하는허딩크 : https://www.youtube.com/live/KtmItpIeYu4?feature=shared
소수 판별만 하면 될 줄 알았는데 예상보다 어렵다.
솔직히 문제도 잘 이해가 가지 않는다.
처음에는 조합으로 해서 최대 조합의 개수를 구하는 건가? 했는데 조건에 두 소수의 합으로 고정되어 있으니
조합을 2개로 제한하고 combinations_with_replacement 함수로 조합의 개수를 구하니 파이썬에서 답은 나왔다.
단, num = 100일때 시간이 좀 걸려서 시간초과가 예상되었다.
<첫번째 시도 : 시간초과>
import sys
import itertools
input = sys.stdin.readline
T = int(input())
for _ in range(T):
num = int(input())
prime_index = [1] * (num + 1)
prime_index[:2] = [0, 0]
for i in range(2, int(num**0.5) + 1):
if prime_index[i]:
for j in range(i*2, num + 1, i):
prime_index[j] = 0
prime = []
for i in range(len(prime_index)):
if prime_index[i]:
prime.append(i)
cnt = 0
for j in itertools.combinations_with_replacement(prime, 2):
if sum(j) == num:
cnt += 1
print(cnt)
<두번째 시도 : 시간 초과>
흠.... 이 문제의 시간을 줄일 수 있는 방법이 너무 궁금해진다.
일단 조금 더 고민을 해보자.
import sys
import itertools
input = sys.stdin.readline
T = int(input())
for _ in range(T):
num = int(input())
prime_index = [1] * (num + 1)
prime_index[:2] = [0, 0]
for i in range(2, int(num**0.5) + 1):
if prime_index[i]:
for j in range(i*2, num + 1, i):
prime_index[j] = 0
prime = [i for i in range(len(prime_index)) if prime_index[i]]
cnt = 0
for i in itertools.combinations_with_replacement(prime, 2):
if sum(i) == num:
cnt += 1
print(cnt)
<세번째 시도 : 시간초과>
하... 감을 못잡겠네.... 이런 방법밖에 생각이 나질 않는데.....
import sys
import itertools
input = sys.stdin.readline
def Prime(n):
graph = [1 for _ in range(n+1)]
graph[0] = graph[1] = 0
for i in range(2, n + 1):
if graph[i] != 0:
for j in range(i*2, n + 1, i):
graph[j] = 0
return [i for i in range(len(graph)) if graph[i]]
T = int(input())
for _ in range(T):
num = int(input())
cnt = 0
for i in itertools.combinations_with_replacement(Prime(num), 2):
if sum(i) == num:
cnt += 1
print(cnt)
<네번째 시도 : 시간 초과>
itertools.combinations_with_replacement를 이중 for문으로 구현해봤는데 역시나 시간초과네.
일단 살짝 구글링을 해봤는데 itertools를 사용하면 안됨. => 이중for문도 금지
import sys
import itertools
input = sys.stdin.readline
def Prime(n):
graph = [1 for _ in range(n+1)]
graph[0] = graph[1] = 0
for i in range(2, n + 1):
if graph[i] != 0:
for j in range(i*2, n + 1, i):
graph[j] = 0
return [i for i in range(len(graph)) if graph[i]]
T = int(input())
for _ in range(T):
num = int(input())
temp = Prime(num)
cnt = 0
for i in range(len(temp)):
for j in range(i, len(temp)):
if temp[i] + temp[j] == num:
cnt += 1
print(cnt)
<다섯번째 시도 : 시간초과>
일단 방향은 주어진 숫자를 반으로 나눠서 각각 +1, -1을 반복해주면서 소수인 경우를 찾는 것이다.
import sys
import itertools
input = sys.stdin.readline
def Prime(n):
graph = [1 for _ in range(n+1)]
graph[0] = graph[1] = 0
for i in range(2, n + 1):
if graph[i] != 0:
for j in range(i*2, n + 1, i):
graph[j] = 0
return [i for i in range(len(graph)) if graph[i]]
T = int(input())
for _ in range(T):
num = int(input())
temp = Prime(num)
a = num // 2
b = num // 2
cnt = 0
while b > 1:
if a in temp and b in temp:
cnt += 1
a += 1
b -= 1
print(cnt)
<여섯번째 시도 : 시간 초과_힌트를 잘못봤음>
import sys
import itertools
input = sys.stdin.readline
def Prime(n):
if n <= 1:
return 0
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return 0
return 1
T = int(input())
for _ in range(T):
num = int(input())
a = num // 2
b = num // 2
cnt = 0
while b > 1:
if Prime(a) and Prime(b):
cnt += 1
a += 1
b -= 1
print(cnt)
아........ 일단 조합을 사용하지 않고 에라토스테네스의체 알고리즘을 사용해서 풀었다. => 이건 동일한데
절반을 나누고 소수인지를 확인하는 작업이 중요함
<일곱번째 시도 : 시간초과>
구글링에 힌트를 참고해서 거의 동일하게 풀었는데 역시나 시간초과가 나오네?? 이거 뭐지??
근데, 내가 참고한 힌트도 시간초과가 나옴.ㅋㅋㅋㅋㅋ잉???? 대부분의 답들이 시간초과가 나오는데? ㅋㅋㅋㅋㅋ 이거 뭐지?
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
num = int(input())
graph = [0, 0] + [1] * (num - 1)
for i in range(2, int(num**0.5) + 1):
if graph[i] != 0:
for j in range(i * 2, num + 1, i):
graph[j] = 0
cnt = 0
for i in range(2, num//2 + 1):
if graph[i] and graph[num - i]:
cnt += 1
print(cnt)
<여덟번째 시도 : 맞았습니다.>
겨우 통과됐다. 백준의 문제 구성은 정말 공부하는데 도움이 되는 것 같다. 처음에는 문제풀기에 급급했으나 나중에는 시간과 메모리까지도 고려를 하게끔 트레이닝을 시킨다.
이번 문제도 진짜 겉으로만 보면 시간초과와 통과가 한 끗차이 같다. 위에 코드는 각각의 정수가 입력될때마다 에라토스테네스의체 알고리즘을 통해서 계산해서 결과값을 보여주지만
아래의 코드는에라토스테네스의체 알고리즘을 1번만 조건의 구간에 완료 한 후 해당 리스트의 인덱스 값으로만 cnt를 진행한다.
import sys
input = sys.stdin.readline
graph = [0, 0] + [1] * (1000000 - 1)
for i in range(2, int(1000000**0.5) + 1):
if graph[i] != 0:
for j in range(i * 2, 1000000 + 1, i):
graph[j] = 0
T = int(input())
for _ in range(T):
num = int(input())
cnt = 0
for i in range(2, num//2 + 1):
if graph[i] and graph[num - i]:
cnt += 1
print(cnt)
와.... 어렵다......코드가 어려운게 아니라 여기까지의 사고 과정이 어렵네....
<다른사람 풀이 참고_좋은 코드 같다.>
코드는 조금 복잡하지만 더 신박한 코드가 있다. (472ms)
1. in list로 해서 찾는 것보다 in set으로 탐색하는게 시간 효율이 좋다. O(n) vs O(1)
ㄴlist로 탐색하면 시간초과됨.
2. "\n".join(list(map(str, answer))) => join에는 str로 이루어진 list가 나와야함.
이 방법도 정말 신박하고 시간이 단축되는 방법이다.
3. 시간을 잡아먹는 리스트 탐색을 set탐색으로 바꾸고, 주어진 입력값 중에 가장 큰 수로 소수를 구한다.
4. 가장 큰 수로 소수 구간을 구했기 때문에 prime > i // 2로 체크를 해줘야한다.
import sys
input = sys.stdin.readline
def main():
T = int(input())
#graph = list(int(input()) for _ in range(T))
graph = [int(input()) for _ in range(T)]
prime_list = Prime(max(graph))
prime_set = set(prime_list)
answer = [0 for _ in range(len(graph))]
for index, i in enumerate(graph):
for prime in prime_list:
if prime > i // 2:
break
if i - prime in prime_set:
answer[index] += 1
#print('\n'.join([map(str, answer)]))
print('\n'.join(list(map(str, answer))))
def Prime(n):
temp = [0, 0] + [1] * (n - 1)
primes = []
for i in range(2, n + 1):
if temp[i]:
primes.append(i)
for j in range(2*i, n + 1, i):
temp[j] = 0
return primes
main()