문제 출처 : [SWEA] 4835 구간합
learn -> course -> programming intermediate -> list1 -> 구간합

문제

N개의 정수가 들어있는 배열에서 이웃한 M개의 합을 계산하는 것은 디지털 필터링의 기초연산이다.

M개의 합이 가장 큰 경우와 가장 작은 경우의 차이를 출력하는 프로그램을 작성하시오.

다음은 N=5, M=3이고 5개의 숫자 1 2 3 4 5가 배열 v에 들어있는 경우이다.

이웃한 M개의 합이 가장 작은 경우 1 + 2 + 3 = 6

이웃한 M개의 합이 가장 큰 경우 3 + 4 + 5 = 12

답은 12와 6의 차인 6을 출력한다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다. ( 1 ≤ T ≤ 50 )

다음 줄부터 테스트케이스의 첫 줄에 정수의 개수 N과 구간의 개수 M 주어진다. ( 10 ≤ N ≤ 100, 2 ≤ M ＜ N )

다음 줄에 N개의 정수 ai가 주어진다. ( 1 ≤ a ≤ 10000 )

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

코드

T = int(input())
for tc in range(1, T + 1):
    num = list(map(int, input().split()))
    num_list = list(map(int, input().split()))

    max_num = 0     # max 값을 저장할 변수
    min_num = 0   # min 값을 저장할 변수

    # 초기화한 변수에 첫번째 구간합을 넣어줌
    for n in range(num[1]):
        max_num += num_list[n]
        min_num += num_list[n]

    # 리스트의 길이에서 벗어나지 않도록 총 길이 - 구간 길이 + 1
    for i in range(num[0] - num[1] + 1):
        # 구간합을 저장할 변수
        sum_num = 0
        # 구간의 길이만큼 반복하면서 값을 저장
        for j in range(num[1]):
            sum_num += num_list[i + j]      # 현재 인덱스인 i부터 구간의 마지막까지 더해줌
        # 구간합이 max_num 보다 크다면 max_num의 값을 구간합으로 바꿔줌
        if max_num < sum_num:
            max_num = sum_num
        # 구간합이 min_num 보다 작다면 min_num의 값을 구간합으로 바꿔줌
        if sum_num < min_num:
            min_num = sum_num

    print(f'#{tc} {max_num - min_num}')

풀이 방법

구간합의 최소, 최대값을 저장할 변수에 우선 첫번째의 구간합을 넣어주었다. 그리고 구간의 길이만큼 반복하면서 값을 저장하고 한 번 구간합을 구한 후에는 최소, 최대값의 변수에 들어있는 값과 비교하여 최소, 최대값을 변경해주었다.