[백준 1912] 연속합(python)

https://www.acmicpc.net/problem/1912

1912번: 연속합

연속합 문제

문제 자체는 사실 엄청 간단하다. 시간 초과만 고려하지않으면 답을 여러개로 뽑아낼 수 있을정도로 간단한 문제지만, 한정적인 시간 안에서 풀어야하는 문제니 나름 까다로웠다고 생각한다.

정답코드

import sys
n = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))

for i in range(1,n) :
    x[i] = max(x[i], x[i-1] + x[i])
print(max(x))

내가 틀린 코드 2와 약간은 흡사한 방법이라고 생각하는데, 사실 x[i]를 굳이 전부 따로 합해주거나 할 필요 없다는 점은 알고 있었으나, 그걸 구현했음에도 시간 초과가 떴는데 이렇게까지 간단하게 될 줄은 사실 생각 못했다.

아직 구현에 대한 이해도가 많이 부족함을 느끼게된 문제였다.

내가 틀린 코드 1

import sys
n = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))
t = [] # 예상 원인
for i in range(n):
    a = [] # 예상 원인
    for j in range(n):
        a += [sum(x[j:i+j+1])] # 예상 원인
    t += a[:n-i] # 예상 원인
print(max(t))

사실 첫번째 코드는 안될걸 각오하고 시도해보았다. 이유는 큰 틀을 잡기 위해서였고, 역시나 시간초과가 떳다.

원인은 크게 리스트를 받아 추가하는 과정으로 인해서 탐색시간이 늘어난다는 점이었다.

내가 틀린 코드 2

import sys
n = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))
y = x[:] # 예상 원인
a = 0
for i in range(n):
    for j in range(n):
        if i < j:
            y[i] = max(x[i], sum(x[i:j]), y[i]) # 예상 원인
print(max(y))

두번째 코드는 사실 될줄 알았다. 물론 리스트를 깊은 복사를 활용해서 하나를 만들어서 max값을 비교해주는 과정을 넣어서 최대한 리스트를 받는 과정을 제거했으나, 역시나 시간초과가 떴다. 원인을 생각하다가 sum함수가 들어간 순간 합쳐가면서 탐색하는 시간이 굉장히 길어지는 것을 깨달아 sum함수도 제거해보기로 했다.

내가 틀린 코드 3

import sys
n = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))
sums = 0
for i in range(n):
    a = 0
    for j in range(n):
        if i+j < n :
            a += x[i+j] # 예상 원인
            if sums < a :
                sums = a
print(sums)

세번째 코드 만큼은 정말 성공할 줄 알았다. 리스트를 추가로 받지도 않았고, sum 함수 또한 제거해서 사용해줬으니 충분히 가능성 있다고 생각했으나.. 메모리 초과의 늪으로 들어가버렸다😥 정말 괜찮은 아이디어였다고 생각했는데 시간만 고려하다보니 메모리는 고려하지 못해서 발생한 원인이었다.

---

느낀점

정말 조금만 더하면 자력으로 풀 수 있었을거 같았던 문제지만 잘 안돼서 너무 아쉬웠다.

점점 문제를 풀수록 시간 복잡도 & 메모리 까지 따져야하니까 많이 정신없는거 같지만, 점점 그래도 이것저것 시도해보면서 실력이 늘어나는 느낌이 들어 좋았다!