# [백준] 1912번 - 연속합

- Author: @mildsalmon
- Published: 2021-09-05
- Updated: 2021-09-06
- Source: http://blex.me/@mildsalmon/%EB%B0%B1%EC%A4%80-1912%EB%B2%88-%EC%97%B0%EC%86%8D%ED%95%A9
- Tags: 파이썬, 알고리즘, 코딩테스트, 문제, 다이나믹프로그래밍, 백준, 실버

---

# 1. 연속합

- 난이도
	- 실버 2
- 시간 제한
	- 1초
- 메모리 제한
	- 128 MB
- 출처
	- [1912번: 연속합 (acmicpc.net)](https://www.acmicpc.net/problem/1912)

### A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

### B. 내 답안

##### a. 1차 제출 (틀림)

```python

n = int(input())  
array = list(map(int, input().split()))  
answer = -1001  
  
for i in range(len(array)):  
    for j in range(0, len(array)):#, i+1):  
 start = j  
        end = j + i+1  
 answer.append(sum(array[start:end]))  
        # print(answer)  
  
print(max(answer))

```

##### b. 2차 제출 (틀림)

```python

n = int(input())  
array = list(map(int, input().split()))  
answer = -1001  
  
A = sorted(array, reverse=True)  
B = []  
# print(A)  
for i in A:  
    B.append(array.index(i))  
  
# print(B)  
big = B[0]  
start = 0  
end = len(B)-1  
for i in range(len(B)):  
    if B[i] <= B[0]:  
        answer = max(answer, (sum(array[B[i]:B[0]+1])))  
        start = i  
    else:  
        answer = max(answer, (sum(array[B[0]:B[i]+1])))  
        end = i  
    answer = max(answer, sum(array[B[start]:B[end]+1]))  
  
print(answer)

```

##### c. 3차 제출 (틀림)

```python

n = int(input())  
array = list(map(int, input().split()))  

answer = []  
answer.append(sum(array))  
  
for i in range(len(array)-1):  
    if array[0] >= array[-1]:  
        array.pop()  
    elif array[0] < array[-1]:  
        array.pop(0)  
    answer.append(max(answer[-1], sum(array)))  
  
print(max(answer))

```

##### d. 4차 제출 (통과)

```python

n = int(input())  
array = list(map(int, input().split()))  

answer = []  
answer.append(array[0])  
for i in range(1, n):  
    answer.append(max(answer[i-1]+array[i], array[i]))  
  
print(max(answer))

```

##### a. 회고

> 풀이

예시를 풀어보면 아래 그림처럼 나온다.

![](https://static.blex.me/images/content/2021/9/6/5_CTcPMAwlSaV4vtmdkmH4.jpg)

하지만 기술한 연산들을 전부 수행하기에는 불필요한 시간이 많이 소요된다. 그래서 아래 그림처럼 불필요한 연산을 제거할 수 있다.

![](https://static.blex.me/images/content/2021/9/6/5_CO1mIFSSjUsMxcUvsRYz.jpg)

하지 않아도 되는 연산을 제외하고 연속된 두 수의 합을 구하여 더 큰 수를 선택하면 해결할 수 있다.

> 반성

맞다고 확신한 방식이 틀렸을때, 어떻게 해야할지를 몰랐었다. 이건 뭐 더 연습해야지, 어쩔 수 없다.

> 결론

- 아직도 c번이 통과하지 못하는 이유가 뭔지 잘 모르겠다. 전체합에서 리스트의 맨 앞과 맨 뒤 수 중 작은 수를 제외한 나머지 전체 합이 이전 전체 합보다 크냐 작냐를 보는 건데.. 왜 안되는걸까.

# 참고문헌

[1912번: 연속합 (acmicpc.net)](https://www.acmicpc.net/problem/1912). Baekjoon. (accessed Sep 5, 2021)

#코딩테스트 #알고리즘 #문제 #파이썬 #백준 #다이나믹프로그래밍