링크 : https://www.acmicpc.net/problem/1644
코드
import sys
input = sys.stdin.readline
N = int(input())
res = 0
decimal = []
for i in range(2,N+1):
check = True
for j in range(2, int(i**(0.5)+1)):
if i%j == 0:
check = False
break
if check:
decimal.append(i)
prefixSum = [0]
for i in decimal:
prefixSum.append(i+prefixSum[-1])
len_prefix = len(prefixSum)
cal_mid = lambda x, y : int((x+y)/2)
for i in range(len_prefix):
lo = i
hi = len_prefix
mid = cal_mid(lo, hi)
while lo+1 < hi:
check = prefixSum[mid] - prefixSum[i]
if check == N:
res += 1
break
elif check > N:
hi = mid
mid = cal_mid(lo, hi)
else:
lo = mid
mid = cal_mid(lo, hi)
print(res)
아이디어
제한조건 : 1<= N <= 4,000,000인 N이 있을 때, 하나 이상의 중복없는 연속된 소수의 합으로 나타낼 수 있는 경우의 수
1. N이하 소수를 다 확인하기
2. N이하 소수를 가지고 구간합을 만들기. (문제 조건에 소수는 꼭 연속되어있어야하고(7+13 = 20 X. 11이 없음.) 중복이 없어서 구간합 문제인걸 확인
3. 구간합을 순회하며 연속된 소수로 표현 가능하면 체크.
오류
- 3번 구간합 순회에서 처음에는 이중for문으로 했는데 시간초과. 그래서 구간합을 앞에서 부터 하나씩 고르고, 그 뒤에 있는 나머지들을 이진탐색으로 돌도록 수행. 추가로 어차피 중복된 수가 구간합에 없을테니 발견하면 break로 탈출
- 이런 직관적인 문제는 금방 풀리는데... 봐도 안떠오르거나 방법이 떠올라도 구현을 어떻게 바꿔야할지 고민되는 문제는 너무 안풀린다... 문제 분석이나 정 안풀리면 일단 답을 찾아서 공부하는 것도...
'알고리즘' 카테고리의 다른 글
프로그래머스 - 오픈채팅방 (0) | 2022.12.17 |
---|---|
프로그래머스 - 길 찾기 게임 (0) | 2022.12.15 |
프로그래머스 - 신고 결과 받기 (0) | 2022.12.07 |
프로그래머스 부대복귀 (0) | 2022.12.06 |
[Python] 백준 10989 - 수 정렬하기 3 (0) | 2022.10.10 |