Koala - 5기/코딩테스트 준비 스터디

[BOJ / Python] 2435 - 기상청 인턴 신현수

IT Act. 2022. 2. 6. 22:32

문제 링크

https://www.acmicpc.net/problem/2435

 

2435번: 기상청 인턴 신현수

첫째 줄에 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 주어진다. N은 온도를 측정한 전체 날짜의 수이다. N은 2이상, 100이하이다. K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사

www.acmicpc.net


풀이

  • 입력받은 온도의 누적합(psum)을 구합니다.
    • 온도를 측정한 날짜 N+1의 길이로 배열 psum을 만듭니다. (line 3)
    • N+1인 이유는 첫째날이 포함되어 계산 시(left-1) 오류가 나지 않게 하기 위함입니다. (배열 맨 앞에 0을 추가)
    • 반복문을 돌며 그 전날까지의 누적합과 해당 날짜의 온도를 더해줍니다. (line 5 ~ 6)
  • 투 포인터를 이용해 연속된 일수의 부분합을 구합니다.
    • k일의 온도가 3 -2 -4 -9 0 3 7 13 8 -3 로 주어졌다면, 누적합은 0, 3, 1, -3, -12, -12, -9, -2, 11, 19, 16 일것입니다. 여기서 13, 8의 온도를 기록한 날들의 합이 최대임을 알려면 19와 -2의 차를 구해야합니다. (line 12)
    • ans값보다 크다면 ans값을 바꿔주고, left와 right를 각각 1만큼 올립니다. (line 12 ~ 14)

코드

n, k = map(int, input().split())
arr = [*map(int, input().split())]
psum = [0]*(n+1)

for i in range(1,n+1):
    psum[i] = psum[i-1]+arr[i-1]

left, right = 1, k
ans = float('-inf')

while right<n+1:
    ans = max(ans, psum[right]-psum[left-1])
    left+=1
    right+=1

print(ans)