BOJ 백준 2559번 문제 <수열> python, 문제 해석 및 풀이

 

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

2559번: 수열

---

문제에 대한 간단한 이해

수열이 주어졌을때 연속된 몇개의 수열 합의 최댓값을 구하는 문제입니다.

입출력에 대한 이해

수열과 수열의 길이, 몇개의 연속된 숫자일지가 주어집니다.

문제에 대한 세부 이해

1. 주어진 것(입력값)

2. 구하고자 하는 것(출력값)

둘 다 위와 같습니다.

 

3. 규칙

몇개의 수열이 연속될지에 따라 합을 구해야 하는 수열의 개수가 달라집니다.

 

- 첫 번째 방법으로는 모든 합을 구 하는 방법을 생각할 수 있습니다. 다만 문제에서 K의 범위(합해야 하는 숫자의 갯수)가 1부터 N까지 이므로 합을 한번 구하는 데 O(N)의 시간이 걸립니다. -> (시간복잡도는 구글링을 통해 이해 바랍니다.)

따라서 이 방법으로 N개의 인덱스들을 돌며 각 수열에 대해 구한다면 시간복잡도상 O(N^2)의 시간이 걸립니다.

 

- 연속된 수열에 대한 합이 필요한 것이므로 변하는 것과 변하지 않는 것을 구분하여 생각합니다.

변하는 것: 사라지는 수열의 맨 앞, 추가되는 맨 뒤 숫자

변하지 않는 것: 나머지 숫자들

-> 합이 변할 때 맨 앞, 맨 뒤 숫자만 생각하면 되는 것을 알 수 있습니다.

 

- 합을 나타내는 변수를 이용해서 인덱스를 하나씩 지나갈 때마다 사라질 숫자와 추가될 숫자의 차이만큼만 합에 더해주고 최대값을 갱신해줍니다.

 

구현

- 구현 자체는 크게 어렵지 않으므로 주석을 참고해주세요

N, K = map(int, input().split())
num_list = list(map(int, input().split()))

sum = 0
# 맨 앞의 첫 수열의 합을 구함
for i in range(K):
    sum += num_list[i]

max_sum = sum
# 그 다음 부터는 합을 일일이 다 구하지 않음 O(N*K)시간 복잡도
# 대신 O(N)시간 복잡도를 가지도록 앞 뒤 차이만 계산해서 더 함
for idx in range(len(num_list)-K):
    back = idx + K
    sum -= num_list[idx]
    sum += num_list[back]

    # 최댓값일 시 갱신
    if sum > max_sum:
        max_sum = sum

print(max_sum)

---

우스갯소리로 스타벅스 출입증이라 불리는 맥북을 사서 스타벅스를 왔다.

맥북에어 m2! 2년간 잘 부탁해~