https://www.acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 N이 100,000 이하기 때문에 이중 for문으로 풀면 시간초과가 나는 문제입니다. 따라서 투 포인터를 이용해서 풀어야 합니다. 즉 시작점과 끝 점을 각각 포인트로 잡고 하나씩 이동하면서 해결해야 합니다. 초기조건으로 K개만큼을 더한 후 단일 For문으로 조회하면서 해결합니다.
소스코드
n, k = map(int, input().split())
arr = list(map(int, input().split()))
answer = []
temp = 0
for i in range(k):
temp += arr[i]
answer.append(temp)
for i in range(k, n):
temp += arr[i]
temp -= arr[i-k]
answer.append(temp)
print(max(answer))'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 11051: 이항 계수 2 (Python) (0) | 2024.04.25 |
|---|---|
| 백준 알고리즘 2531: 회전 초밥 (Python) (1) | 2024.04.25 |
| 백준 알고리즘 7795: 먹을 것인가 먹힐 것인가 (Python) (0) | 2024.04.24 |
| 백준 알고리즘 2792: 보석 상자 (Python) (0) | 2024.04.24 |
| 백준 알고리즘 2805: 나무 자르기 (Python) (0) | 2024.04.24 |