[백준] 2559번 수열 - 파이썬 Python 풀이

 

반응형

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

2559번: 수열

 

1. 문제 

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

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다. 

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

입력

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

출력

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

2. 문제 접근

그림의 형태와 주어지는 조건을 시간복잡도 계산을 통해 DP 문제라는 것을 알 수 있었다.

때문에 O(n) 시간복잡도로 문제를 해결해야했다.

 

입력 값

10 2
3 -2 -4 -9 0 3 7 13 8 -3

일 때

누적합을 구한다.

[0, 3, 1, -3, -12, -12, -9, -2, 11, 19, 16]

이 나온다. 0번째는 0으로 빈 값을 두고 1부터 n까지 구한다.

그 다음 

dp[i] - dp[i-k]

점화식을 통해 k일의 온도의 합을 구할 수 있다.

위에 예시로 만약 4일 5일의 온도의 합을 구한다면 dp[5] - dp[5-2]

즉, -12--3 = -9를 구할 수 있다.

이런 방식으로 k부터 n+1까지 K일의 온도의 합이 최대가 되는 값을 구한다.

 

3. 틀린 부분

처음에 제출한 코드다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
graph = list(map(int, input().split()))
dp = [0]*(n+1)

for i in range(1, n+1):
    dp[i]=dp[i-1]+graph[i-1]

answer = 0
for i in range(k, n+1):
    answer = max(answer, dp[i]-dp[i-k])

# print(dp)
print(answer)

예제의 답은 제로 나왔지만 틀렸다.

이유는 답이 음수일 수 있기 때문에 answer의 초기값을 0으로 하면 안되다.

 

만약에 입력이

7 6
-100 -100 -100 -100 -100 -100 -100

주어진다면, 0을 출력한다. 하지만 답은 -600이다.

때문에 answer을 음수 최소값으로 초기화 해야된다. 

 

반응형

 

4. 정답

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
graph = list(map(int, input().split()))
dp = [0]*(n+1)

for i in range(1, n+1):
    dp[i]=dp[i-1]+graph[i-1]

## 핵심
answer = -sys.maxsize
for i in range(k, n+1):
    answer = max(answer, dp[i]-dp[i-k])

# print(dp)
print(answer)