[백준 2208] 보석 줍기 (Python)

www.acmicpc.net/problem/2208

2208번: 보석 줍기

 

문제풀이

N, M, arr : 입력값

prefix_sum : 구간합 

 

단순하면서도 어려운 구간 합(Prefix Sum) 문제였다. 머리로는 이해가 되는데, 설명하기가 굉장히 어려운 풀이이다.. 조금 더 풀이 해설 보완이 필요할 것 같다.. ㅠㅠ

 

1. arr 입력을 받으면서 구간 합을 구한다.

 

2. 인덱스 M - 1 부터 N 까지 최소 구간합을 구하고, 최소 구간합을 뺴주면서 최대 구간합을 구한다.

- 인덱스 M - 1 부터 확인하는 이유는 M - 1 보다 작을 경우 길이 M 이상인 부분 배열을 고를 수 없기 때문

 

3. 결과(가치 최대값)를 출력한다.

 

코드

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    arr = [0] * N
    value = 0
    prefix_sum = [0]
    for i in range(N):
        arr[i] = int(input())
        value += arr[i]
        prefix_sum.append(value)
    ans, tmp = 0, 0
    for i in range(M - 1, N):
        tmp = min(tmp, prefix_sum[i - (M - 1)])
        ans = max(ans, prefix_sum[i + 1] - tmp)
    print(ans)

 

결과

 

위 풀이는 '라이' 님의 C++ 풀이를 참고한 코드입니다.

m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221386454504&proxyReferer=https:%2F%2Fwww.google.com%2F

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!