[백준] 2559번 : 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2559번: 수열

 

1. 문제 설명

2. 풀이과정

문제에서 주어진 시간 제한은 1초이고 N의 최댓값은 100,000이다.

연속적인 날짜의 수가 따로 주어져 해당 날짜의 온도 합이 최대가 되는 값을 구해야 하는 문제이므로 매번 날짜의 온도 합을 구하려면 많은 시간이 소요될 것이다.

하여 투 포인터를 활용해 날짜의 온도 합을 단순 사칙연산으로 빠르게 구할 것이다.

연속적인 날짜의 시작과 끝 위치를 각각 지정하여 구간을 지정한 뒤, 첫 번째 구간의 온도 합을 저장한다.

이후 구간은 유지하면서 각 시작과 끝 위치를 동일하게 옮기며 각 구간별 온도의 합을 구한다.

구간마다 온도의 합을 계산하고 그중 최댓값을 계속적으로 저장한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 패키지를 불러온다. import sys
2. 온도를 측정한 전체 날짜의 수와 연속적인 날짜의 수를 입력받는다. N, K = map(int, sys.stdin.readline().split())
3. 매일 측정한 온도를 입력받아 리스트로 저장한다. T = list(map(int, sys.stdin.readline().split()))
4. 합을 구할 연속적인 날짜의 시작 위치를 저장할 변수를 생성하고 초기화한다. s = 0
5. 합을 구할 연속적인 날짜의 끝 위치를 저장할 변수를 생성하고 연속적인 날짜의 수로 초기화한다. e = K
6. 온도의 합을 저장할 변수를 생성하고 처음 연속적인 날짜 구간의 온도 합을 저장한다. sum_T = sum(T[s : e])
7. 온도의 합 중 최댓값을 저장할 변수를 생성하고 초기 값을 저장한다. MAX = sum_T
8. 연속적인 날짜의 끝 위치가 전체 날짜의 수를 넘어가기 전까지 반복하며 while (e < N)
9. 먼저 구간 시작 위치의 온도를 빼주고 sum_T -= T[s]
10. 구간의 시작 위치를 다음으로 옮긴다. s += 1
11. 구간 끝 위치의 온도를 더해주고 sum_T += T[e]
12. 구간의 끝 위치를 다음으로 옮겨 연속적인 날짜의 구간을 전반적으로 옮긴다. e += 1
13. 만약 새로 구한 온도의 합이 이전의 온도 합 중 최댓값보다 크면 if (MAX < sum_T)
14. 최댓값을 새로 구한 온도의 합으로 저장한다. MAX = sum_T
15. 모든 연속적인 날짜의 온도 합을 확인한 뒤, 최댓값을 출력한다. print(MAX)

반응형

3. 소스코드

import sys

N, K = map(int, sys.stdin.readline().split())
T = list(map(int, sys.stdin.readline().split()))

s = 0
e = K
sum_T = sum(T[s : e])

MAX = sum_T
while (e < N):
    sum_T -= T[s]
    s += 1
    sum_T += T[e]
    e += 1
    
    if (MAX < sum_T):
        MAX = sum_T

print(MAX)