[백준/ 파이썬] 12847번 꿀 아르바이트

김민구·2022년 5월 4일
0

백준 풀이

목록 보기
7/18

백준 12847 꿀 아르바이트

12847번 꿀 아르바이트 문제는 누적합 문제입니다.
모든 경우에 대해서 처음부터 합을 구하는 것이 아니라 이전에 구해놓은 합으로 부터 값을 찾아가는 방식입니다.


제가 예전에 만들어놓은 그림입니다. Sliding window 방식으로 문제를 해결할 수 있습니다.

  1. 맨 처음에는 sum이 필요하기에 m만큼의 sum을 구해줍니다.
  2. 그 다음부터의 sum은 이전의 start와 이후의 end의 합과 차를 통해 구할 수 있습니다.

전체 코드는 다음과 같습니다.

n, m = map(int, input().split())
salary = list(int(x) for x in input().split())

sum = 0
for i in range(m):
    sum += salary[i]

start = 0
end = m
max_sum = sum
while end < n:
    sum = sum + salary[end] - salary[start]
    max_sum = max(max_sum, sum)
    start += 1
    end += 1
print(max_sum)
profile
성장하는 개발자가 되고싶어요😀

0개의 댓글