백준 | 꿀 아르바이트

백준 꿀 아르바이트

단순하게 for 문으로 접근하면 시간 초과가 뜬다. sum()의 시간 복잡도가 O(m)이므로, 아래 코드의 시간 복잡도는 O((n -m + 1) * m)이다.

# 오답

import sys


n, m = map(int, sys.stdin.readline().split())
salaries = list(map(int, sys.stdin.readline().split()))

max_salary = 0
for i in range(n - m + 1):
    salary = sum(salaries[i:i + m])

    if salary > max_salary:
        max_salary = salary

print(max_salary)

위의 코드에서 매번 슬라이싱된 리스트의 합을 구하는 대신, m개의 리스트를 오른쪽으로 한 칸씩 옮길 때 변화되는 값만 고려(슬라이딩 윈도우)하면 된다.

# 정답

import sys


n, m = map(int, sys.stdin.readline().split())
salaries = list(map(int, sys.stdin.readline().split()))

salary = sum(salaries[0:m])
max_salary = salary

for i in range(n - m):
    salary += (salaries[i + m] - salaries[i])
    max_salary = max(max_salary, salary)

print(max_salary)


# import sys


# n, m = map(int, sys.stdin.readline().strip().split())
# wages = list(map(int, sys.stdin.readline().strip().split()))

# wage = sum(wages[:m])
# max_wage = wage

# for i in range(m, n):
#     wage += (wages[i] - wages[i - m])
#     max_wage = max(max_wage, wage)

# print(max_wage)