[맛있는물회] <SWEA 알고리즘> 4835번 "구간합 구하기"

파이썬으로 알고리즘 공부를 시작했다.

아직 문법이 익숙지 않은 것도 있고 알고리즘 손 놓은지 약 4개월이 다 되어간다. 취업을 위해서라도 오늘부터 꾸준히 쉬운문제부터 열심히 해야겠다!! ㅎㅎ

 

문제 조건

---

Input

---

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

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

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

Output

---

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

 

생각한 아이디어

---

아주 기초적인 문제라서 블로그를 찾아올 사람이 있을지는 모르겠지만 적어본다. 정말 간단한 그리디 문제이다. 

테스트 케이스의 개수에 맟는 최대 최소의 범위를 잡아두고 List의 첫번째부터 Sequential하게 나아가면서 끝에 도달하면 계산 후 출력하는 형식이다.

아래의 코드를 보면 아주 쉽게 이해가 갈 듯하다.

소스코드

T = int(input())
for TC in range(1, T+1):
    N,M = map(int,input().split())
    arr = list(map(int,input().split()))

    i = 0
    min = 9999999
    max = -9999999
    while 1:
        sum = 0
        if i+M > N:
            break
        for j in range(i,i+M):
            sum += arr[j]
        if sum>max:
            max = sum
        if sum < min:
            min = sum
        i += 1

    print('#%d %d' %(TC, max-min))