4835. [파이썬 S/W 문제해결 기본] 1일차 - 구간합 / SW Expert Academy

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


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

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

 

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

v

1

2

3

4

5

 

v

1

2

3

4

5

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

v

1

2

3

4

5

이웃한 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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

입력

3
10 3
1 2 3 4 5 6 7 8 9 10
10 5
6262 6004 1801 7660 7919 1280 525 9798 5134 1821 
20 19
3266 9419 3087 9001 9321 1341 7379 6236 5795 8910 2990 2152 2249 4059 1394 6871 4911 3648 1969 2176

출력

#1 21
#2 11088
#3 1090

 

Pass 코드

T = int(input())
t = 1

while T-t >= 0:
    N, M = map(int, input().split())
    ai = list(map(int, input().split()))

    sum = 0
    min = 987654321
    max = 0

    # M 개씩 묶어서 합을 구해서 비교
    # 0부터 M 까지 1+2+3
    # 1부터 M+1 까지 2+3+4 ...
    # N-M 부터 N 까지 하면 종료

    # 전에 더한 값보다 작으면 min 에 크면 max 에 대입
    index = 0
    while index + M <= N:
        for i in range(M):
            sum += ai[index + i]
        if sum < min:
            min = sum
        if sum > max:
            max = sum
        index += 1
        sum = 0
      
    print("#"+str(t), max - min)
    t += 1