[백준 1912] 파이썬 - 연속합

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

1912번: 연속합

 

1. 코드 설명

 

1) 전형적인 dp 풀이 ( 0 행렬을 만들고 채워가는 방식 )

n = int(input())

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

dp = [0] * n

dp[0] = lst[0]

print(dp)

for i in range(1, len(lst)):

    dp[i] = max(lst[i], dp[i-1] + lst[i])

    print(dp)

print(max(dp))

 

 

 

2) append 를 이용한 풀이

n = int(input())

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

answer = []

hap = 0

for x in lst:

    hap += x

    

    answer.append(hap)

    if hap < 0 : 

        hap = 0

        #print('hap 초기화')

    #print(answer)

print(max(answer))

 

 

1) 과 2)의 포인트는 동일하다

 

연산(합)의 결과가 음수일때 이전 연산을 버리는 것이다.

 

1)의 경우 

 

dp[i] = max(lst[i], dp[i-1] + lst[i])

 

이전 연산 ( dp[i-1] + lst[i] )이 현재 값 ( lst[i] ) 보다 낮다면 이전 연산을 버리는 방식이고

 

2)의 경우

if hap < 0 :   hap = 0

이전 연산( hap ) 이 음수라면 이전 연산을 0 으로 초기화하는 방식으로 버리는 방식이다.

 

 

 

 

 

 

2.  주의사항

n= int(input())

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

hap = []

for i in range(n) :

  for j in range(i+1,n) :

    hap.append(sum(lst[i:j]))

print(max(hap))

 

전체 탐색하여 모든 조합을 고려하는 것은 당연하게도 시간초과가 발생한다

 

앞으로 모든 조합을 고려하는 코드는 지양해야겠다

 

 

 

 

또한 dp 풀이에서 초항을 설정하는 것이 아주 중요하다

 

dp[0] = lst[0]

 

dp 풀이에선 인덱스 오류가 아주 빈번하게 발생하는데 대부분 초항에 대한 문제이다.