[백준][파이썬] 2559번 수열

 2559번 : 수열

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

링크

2559번: 수열 (acmicpc.net)

2559번: 수열

 

 접근 방법

1. n, k 값과 수열(temp)을 입력 받는다.
2. 가능한 수열의 첫번째 부분 합(part)을 구한다.
3. ans(정답) 변수의 값을 part로 초기화 한다. (나중 max 함수 사용을 위해)
4. 가능한 경우의 수(n-k-1) 만큼 for문을 통해 반복한다.
   1. 가능한 수열의 부분 합(part)을 구한다.
   2. 최댓값을 구하기 위해 max 값을 사용하여 ans 값을 구한다.
5. ans 값을 출력한다.

+ 투포인터 참고 자료 : [알고리즘] 투 포인터(Two Pointers) — y-seo의 딩코 기록들 (tistory.com)

[알고리즘] 투 포인터(Two Pointers)

 

 풀이

 

1. 슬라이딩 윈도우

처음에는 이중 for문으로 문제를 풀기도 하고 for문 안에 sum 함수를 사용하는 식으로 코드를 짜기도 하였다. 그러나 돌아오는 것은 빨간색 글씨의 시간 초과..

이중 for문이나 sum 함수는 반복문의 가능한 범위에 따라서 시간 초과가 날 수도 있다. 이 문제에서는 n 값이 10만이니 더욱 그럴 수 밖에..

따라서 슬라이딩 윈도우 방법을 통해 시간 효율을 벌어주어야 한다.

슬라이딩 윈도우란 특정 범위(윈도우)가 있을 때 윈도우 내부 요소의 값을 이용해 문제를 풀이하는 알고리즘이다. 이 방법을 사용하면 sum 함수 없이도 부분 합을 구할 수 있다.

이번 문제에서는 아래와 같이 활용하였다.

part = sum(temp[:k]) #첫번째 경우의 합
ans = part

for i in range(0, n-k): #가능한 경우의 수
    part += temp[i+k] - temp[i] #슬라이딩 윈도우
    ans = max(ans, part)

우선 temp[0]부터 temp[k-1] 까지의 원소는 sum 함수를 이용해 part 변수에 저장해주었다. 이는 문제에 주어진 리스트를 순서대로 생각했을 때 가장 먼저 접근할 수 있는 경우의 수이다. 예를 들면 2일 동안의 온도의 합을 구할 때는 part = temp[0] + temp[1]이 되겠다. 이를 슬라이싱을 이용해 sum(temp[:k])로 나타내었다.

이후 가능한 모든 경우의 수(n-k-1)동안 part 값을 변경시켜줄 것이다. 위와 같은 예시에서 생각해보면 다음으로 생각할 수 있는 경우의 수는 temp[1] + temp[2]가 되겠다. 따라서 이미 구한 part에서 temp[0]은 빼주고 temp[2]를 더해주면 된다. 이와 같은 생각을 코드로 나타내면 part += temp[i+k] - temp[i] 가 된다. 

이후 기존 ans와 새로 구한 part 값 중 max 함수를 이용해 최댓값만 남기면 문제에서 요구하는 정답을 찾을 수 있다.

 

 전체코드

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
temp = list(map(int,input().split()))

part = sum(temp[:k]) #첫번째 경우의 합
ans = part

for i in range(0, n-k): #가능한 경우의 수
    part += temp[i+k] - temp[i] #슬라이딩 윈도우
    ans = max(ans, part)

print(ans) #최댓값 출력