[백준] 1912번 : 연속합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1912번: 연속합

 

1. 문제 설명

2. 풀이과정

문제가 자꾸 시간초과가 나서 문제를 어떻게 계속 접근을 할지에 대해 고민하다가 알고리즘 분류에서 다이나믹 프로그래밍을 참고하여 해결하였다.

수열 중 합이 최대가 되도록 하기 위해 첫 번째 원소부터 마지막 원소까지 자신과 자신 + 앞 원소를 비교하여 더 큰 값을 저장하도록 구현하고 마지막에 제일 큰 값을 찾도록 구현하였다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 전체 수의 개수를 입력받는다. n = int(sys.stdin.readline())
3. 다음 줄에 공백을 기준으로 하여 수를 입력받아 리스트로 저장한다. li = list(map(int, sys.stdin.readline().split()))
4. 앞 원소가 필요하기 때문에 두 번째 원소부터 마지막 원소까지 인덱스 한다. for i in range(1, len(li))
5. 해당 자리 값을 원래 해당 자리의 값과 바로 앞 원소를 더한 값, 두 값을 비교하여 더 큰 값으로 다시 저장한다. li[i] = max(li[i], li[i] + li[i - 1])
6. 마지막 원소까지 비교하여 결과를 저장했다면 새로 저장한 리스트의 원소들 중 최댓값을 출력한다. print(max(li))

반응형

3. 소스코드

import sys

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

for i in range(1, len(li)):
    li[i] = max(li[i], li[i] + li[i - 1])

print(max(li))