[코드트리 챌린지] 구간 중 최대 합/ 완전탐색

 

https://www.codetree.ai/missions/5/problems/max-sum-of-subarray?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

구간 중 최대합

---

n개의 숫자들이 주어졌을 때, 연속하여 k개의 숫자를 골랐을 때의 합이 최대가 되도록 하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에는 n과 k가 주어집니다.

두 번째 줄에는 n개의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ k ≤ n ≤ 100
• 1 ≤ 주어지는 숫자 ≤ 100

출력 형식

첫 번째 줄에 최댓값을 출력합니다.

 

입출력 예제

예제1

입력:

6 3
9 1 2 4 7 1

출력

13

 

---

 

 

내가 짠 코드

---

n, k = tuple(map(int, input().split()))

arr =   list(map(int, input().split()))

m_sum = 0
for i in range(0, n-k+1):
    sum = 0
    for j in range(i, i+k):
        sum = sum +  arr[j]
    m_sum = max(sum,m_sum )


print(m_sum)

우선 n, k , 수 배열을 입력받는다. 그 후 1부터 배열의 길이까지 순회하며 하나의 수를 정하여 그 수부터 k개까지의 연속된 수의 합을 구한다. 그 합의 최댓값을 구해야한다. 

처음에는 arr[0]~arr[0+k-1] 까지 의 합을 구할 것이고 

다음은 arr[1] ~ arr[1+k-1] 까지의 합을 구할 것이고 

 

i번째면 arr[i] ~ arr[i+k-1] 까지의 합을 구할 것이다.

 

마지막은 

arr[n-k+1] ~arr[n-1]까지의 합을 구하므로 

 

 

i의 범위설정에 유의해야한다. 

그 후 sum 을 비교해가면 된다.