Algorithm & Problem Solving/구간 합(Prefix Sum)
[백준 2208] 보석 줍기 (Python)
baby_ohgu
2021. 1. 4. 23:39
2208번: 보석 줍기
화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1≤N≤100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득을
www.acmicpc.net
문제풀이
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++ 풀이를 참고한 코드입니다.
문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!