[Python] 1912. 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

n개의 정수로 이루어진 임의의 수열이 주어지는데, 연속된 몇개의 수의 합 중 가장 큰 합을 구하려고 한다. 

단, 하나의 수는 필수로 선택해야 한다.

 

---

이 문제는 삽질의 끝판왕이었던 문제였다.

 

우선 코드부터 보고 이야기 해보도록 하자.

def sol(data) :
    ans= []
    for i in range(len(data)):
        for j in range(len(data[i:])):
            ans.append(sum(data[i:i+j]))
    return max(ans)

n = int(input())
arr = list(map(int, input().split()))
print(sol(arr))

우선 sol이라는 함수부터 선언했다.

코드를 한줄 한줄 읽어보면, data로 전달받은 리스트를 이용해 i와 j를 이용해 순회하면서 모든 경우에 대한 합을 ans리스트에 저장하고, 그 중에서 ans의 최댓값을 리턴하도록 했다.

그의 결과로...

 

그러나 너무나 당연한 결과였다.

알고리즘이라곤 1도 없어보이는 코드였다 ..;;

 

그러던 중 순회를 하기는 하지만, 새로운 방법을 적용해보기로 했다.

n = int(input())
arr = list(map(int, input().split()))
val = arr[0]
max_val = arr[0]
for t in arr[1:]:
    if val <0 and t >0 :
        val = t
    else :
        val += t
    max_val = max(max_val, val, t)
print(max_val)

일단 max_val과 val이라는 변수에 리스트의 첫번째 요소를 넣고 시작했다.

여기서 val은 지금 진행중인 연속합에 해당하는 요소이고, max_val은 그 시점까지의 최댓값을 갖게 하는 방법이었다.

 

그래서 만약 전에 입력한 val값이 음수이고(지금까지의 연속합이 음수이고), 현재 값이 양수이면 val 변수에 t를 넣어줬고(새로운 연속합의 시작으로 간주하기로 하고), 만약 아니라면 그 당시가 최댓값을 가지는 연속합의 요소라고 간주한다.

 

마지막에 max_val은 이제 그 시점에서 세 변수의 최댓값을 구함으로써 연속합을 구현할 수 있었다.