[Baekjoon]백준 2559 수열(실버 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 n개의 수를 입력을 받게 되고, 연속적인 k개의 합 중에서 가장 큰 값을 출력하는 문제이다

가장 간단한 방법이라 함은, k개의 index를 묶어 for문을 통해 이동하며 sum함수로 합을 구하는 것이다

하지만, 여태까지 백준 문제를 푼 경험으로 보아 그런 문제는 아닐것이다

 

그래서 효율적인 방법이 뭐가 있을까라는 생각을 하다가 합을 구하는 부분에서 아이디어가 생각났다

이전의 index의 값들도 포함하여 더하기때문에, 굳이 해당 index안의 값들을 다 더할 필요가 없다는 것이다

다시 말하자면, 1 2 3 4 5 3 2 1 이라는 리스트가 존재하고, k가 3이라고 가정해보자

 

처음에 말한 간단한 방법으로 수행하면 1 2 3의 합을 구하여 6을 저장하고, 2 3 4 의 합을 구하여 9를 저장할 것이다

두 번째 방법으로 수행하게 된다면 1 2 3 을 더한 값을 이용하여 다음 index의 부분합을 구할 수 있다

result에는 6이라는 수가 저장되어있을것이고, 이 수는 index가 0, 1, 2인 경우의 합이다

result의 다음 index에는 index가 1, 2, 3인 경우의 합을 저장하기 때문에 index가 3인 경우를 

result의 값에 더해주고, index가 0인 경우의 값을 빼주면 더 간단한 방법으로 부분합을 구할 수 있다

 

이를 코드로 나타내기 위해 처음의 index부터 k까지의 리스트 합을 result리스트에 저장해주고,

그 뒤의 값들은 for문을 통해 저장해주면 된다

num, cnt = map(int, input().split())
ls = list(map(int, input().split()))

result = []
result.append(sum(ls[0:cnt]))

for i in range(num - cnt):
    result.append(result[i] + ls[i + cnt] - ls[i])
    
print(max(result))

이렇게 하면 합을 구하는 과정에서 불필요한 계산을 하지 않고 최댓값을 구할 수 있다