[백준]1912 연속합(Python)

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

1912번: 연속합

 

문제 접근

 

이 문제는 보자마자 dp라고 생각하긴 했다...

리스트의 0,1 ... N까지에서 가장 큰 합을 차곡차곡 dp테이블에 저장하자!

한 시간 동안 열심히 풀었는데 조건의 분기를 잘못했는지 틀렸다. 

 

코드

 

틀린코드 => 테케를 손으로 써보면 틀리긴 함....

import sys
input = sys.stdin.readline

N = int(input())

dp = [0 for _ in range(N)]

nums = list(map(int, input().split()))

dp[0] = nums[0]
dp[1] = max(dp[0], dp[0]+nums[1], nums[1])  #여기까진 맞..

for i in range(2, N):
    if dp[i-2] == dp[i-1]:
        dp[i] = max(nums[i], dp[i-1])
    else:
        dp[i] = max(nums[i], dp[i-1]+nums[i], dp[i-1])
    print(dp[i])

print(dp[N-1])

import sys
input = sys.stdin.readline

N = int(input())

dp = [0 for _ in range(N)]

nums = list(map(int, input().split()))

dp[0] = nums[0]
for i in range(1, N):
    dp[i] = max(nums[i], dp[i-1]+nums[i])

print(max(dp))

 

회고

 

조건이 틀렸다 싶으면 바로 다른 조건을 생각해 보고 조금 더 쉽게 접근하는 것을 찾아야 하는데 자꾸 저 조건이 맞고 max의 비교 대상을 늘렸다가 줄였다가 반복하는 등 헛짓을 해버렸다.. 

생각보다 너무 답이 단순하다...