728x90
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
백준 2230 <수 고르기>
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우
dev-diary-0717.tistory.com
전형적인 투포인터 문제로 2230 번 문제에서 조건만 달라진 문제입니다.
def solution(N, M, data_list):
# 누적합을 편하게 만들기 위해 0 추가
data_list = [0] + data_list
# 누적합 생성
for idx in range(1, len(data_list)):
# 누적합
data_list[idx] += data_list[idx-1]
# 투포인터
start = 0
end = 1
# 카운트
cnt = 0
while True:
# end 가 인덱스를 벗어나면
if end >= len(data_list):
return cnt
# 포인터 값
start_value = data_list[start]
end_value = data_list[end]
# 누적합
subsum = end_value - start_value
# 누적합이 목표값보다 크면
if subsum > M:
start += 1
continue
# 누적합이 목표값보다 작으면
elif subsum < M:
end += 1
continue
# 누적합이 목표값이면
else:
cnt += 1
end += 1
continue
N, M = map(int, input().split())
data_list = list(map(int, input().split()))
print(solution(N, M, data_list))
728x90
'Coding Test > BaekJoon_Python' 카테고리의 다른 글
| 백준 11725 <트리의 부모 찾기> Python (1) | 2023.11.13 |
|---|---|
| 백준 1991 <트리 순회> Python (0) | 2023.11.13 |
| 백준 1644 <소수의 연속합> Python (0) | 2023.11.10 |
| 백준 2668 <숫자고르기> Python (0) | 2023.11.09 |
| 백준 2230 <수 고르기> Python (0) | 2023.11.09 |