[12847] 꿀 아르바이트(python)

1. 문제

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

12847번: 꿀 아르바이트

 

2. 구현 과정

- 시간 제약이 1초이므로, O(N^2)만 되어도 안된다. N의 범위가 10만이므로, 최대 NlogN으로 풀어야 한다.

-  누적합 함수인 accumulate를 사용해서 dp형식으로 푸는 방법과 투 포인터를 사용하는 방식 두 가지 방식으로 풀 수 있다. 개인적으로 투 포인터 문제는 익숙치 않아서, 후자 푸는 연습을 해야할 듯!

 

-  for문 두 번 돌리는 방법 

for i in range(0, n-m):
    pay_sum = 0
    for j in range(i, i+m):
        pay_sum += pay[j]
    answer = max([answer, pay_sum])

투 포인터를 사용해서 이중 포문을 포문 하나로 바꾸는 법

 pay_sum = sum(pay[0 : m])

for i in range(0, n - m):
    pay_sum += pay[i + m] - pay[i]

 

위 방식으로 가장 큰 pay_sum값을 리턴한다.

 

 

3. 실수한 것 & 처음 안 것

- from itertools import accumulate : list의 누적 합을 차례로 출력해줌

 

4. 코드

from itertools import accumulate

N,M = map(int,input().split())
pays = list(map(int,(input().split())))
sum_list = list(accumulate(pays))
dp = [0] * N

for x in range(N):
	if x < M:
		dp[x] = sum_list[x]
	else:
		dp[x] = max(dp[x-1],sum_list[x] - sum_list[x-M])

print(dp[N-1])


---------------------------------------------
N,M = map(int,input().split())
pays = list(map(int,input().split()))

answer = sum_pays = sum(pays[0:M])

for i in range(0, N-M):
    sum_pays += pays[M+i] - pays[i]
    answer = max( answer, sum_pays )
print(answer)