[BOJ] 1912번 연속합 / 사용언어 : 파이썬(python)

※ 문제링크

1912번: 연속합

해당문제는 규칙을 확인하고 동적 프로그래밍으로 풀어야하는 문제였다. 포도주 시식, 계단 오르기 문제와 거의 비슷한 개념으로 접근하면 생각보다 쉽게 풀 수 있는 문제였다. 내가 사용한 풀이방법과 코드는 아래와 같다.

<풀이방법>

- 첫번째에서 가질 수 있는 값은 자기 자신과 동일

- 2번째 부터는 dp에 저장된 i-1번째 값과 자기자신을 더한 값과 자기자신중 더 큰 값을 반환 후 저장 

1. 숫자를 저장할 리스트와 최댓값을 저장할 리스트를 생성한다.

2. 연속하는 숫자들을 더했을 때의 최댓값을 해당 인덱스에 맞춰 계산하고, 그 값을 저장한다.

3. 마지막까지 계산 후 그 중 최댓값을 출력한다.

 

N = int(input())
num_list = list(map(int, input().split()))
dp = [0 for _ in range(N)]
dp[0] = num_list[0]
for i in range(1,N):
    dp[i] = max(num_list[i], dp[i-1] + num_list[i])
print(max(dp))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.