[BOJ | python] 2559번: 수열

 

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

 

문제

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

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

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

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

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

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

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

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

 

입력

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

 

 

출력

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

 

풀이

1. 처음 풀이

N, K = map(int, input().split())
li = list(map(int, input().split()))
left, right = 0, K - 1 		# 투 포인터 초기화 (간격: K)
temp = li[left] 	# while문 첫 줄에 temp += li[right]하기위한 초기화
max_value = 0 		# 최댓값 0으로 초기화

while right < N:
    temp += li[right] 		
    # left, right가 바뀔 때마다 temp값을 새로 설정하는 게 아닌
    # 기존 temp값에서 li[left]를 빼고 새로운 li[right]를 더하기 위한 코드
    # right의 범위가 벗어나는 걸 방지하기 위해 while문 바로 아래에서 right를 더함
    
    max_value = max(max_value, temp) 	# temp와 max_value 중 더 큰 값을 max_value로 설정
    temp -= li[left] 		# 기존 temp값에서 left를 빼고 right를 더하는 과정
	
    # 투 포인터 값 변경
    left += 1
    right += 1

print(max_value)

 

첫 예제는 통과하였으나, 두 번째 예제는 틀린 값이 나왔다.

 

 

2. 디버깅

N, K = map(int, input().split())
li = list(map(int, input().split()))
left, right = 0, K - 1
temp = li[left]
max_value = 0

while right < N:
    temp += li[right]
    print("Temp:",temp)  # print 추가
    max_value = max(max_value, temp)
    temp -= li[left]

    left += 1
    right += 1

print(max_value)

 

어느 부분이 문제인지를 확인하기 위해, temp값을 중간중간 보기 위한 print문을 추가하였다.

출력

문제에 의하면 -12, -12, -3...의 값이 나와야 하는데, 처음 값부터 잘못된 것을 알 수 있었다. 

이유인 즉슨 temp의 초깃값을 li[left] ~ li[right-1]의 합으로 설정했어야 하는데, 첫 예제에서 K가 2라서 이 부분을 간과한 채 초깃값을 li[left]f로만 설정한 것이 문제였다.

 

3. 풀이 수정

N, K = map(int, input().split())
li = list(map(int, input().split()))
left, right = 0, K - 1
temp = sum(li[left : right])  # 초깃값 변경
max_value = 0

while right < N:
    temp += li[right]
    print("Temp:",temp)
    max_value = max(max_value, temp)
    temp -= li[left]

    left += 1
    right += 1

print(max_value)

 

따라서 temp의 초깃값을 적절하게 수정했다.

예제에 대한 출력도 잘 나옴.

 

맞왜틀?

40 몇 퍼까지 가다가 틀려버림...

 

4. 또버깅 (예외찾기...)

온도가 모두 음수로만 주어질 경우, 최댓값을 0으로 초기화한 것이 문제가 될 것 같아 max_value의 초깃값을 temp로 설정했으나 여전히 틀렸다..

그리고 또 생각해보니, 모두 음수일 경우에 max_value를 temp로 설정할 경우, li[right]의 값이 빠져있으므로 당연히 실제 temp보다 max_value가 더 클 것이라는 생각이 들었다. 따라서 max_value를 temp + li[right]로 초기화함으로써 해결할 수 있었다...

 

초기화를 잘하도록 하자.