백준 13398 연속합 2 파이썬

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

13398번: 연속합 2

처음에 이 문제를 봤을때 숫자를 뺀 경우 and 그냥 연속합 두가지 부분으로 나눠서 풀어야 겠다는 생각이 들었다.

그래서 2차원 리스트를 만들어 줬다.

코드 설명은 코드에 주석을 달아두겠습니당.

더 밑에는 주석 없는 버전 코드도 올려두겠습니다.

 

n = int(input())
s = list(map(int,input().split()))
dp = [[0]*n for _ in range(2)] # 연속합 and 하나 제외 연속합 리스트
for i in range(n):
    if dp[0][i-1]+ s[i]>=0:#합이 0보다 크거나 같다면 더해준다. 
        dp[0][i]=dp[0][i-1]+ s[i]


    if dp[1][i-1] +s[i]>=0:#하나 제외 연속합 리스트의 값이 0보다 크다면 더해준다.
        if s[i]<0: #이번에 더할 수가 만약에 음수면 
            dp[1][i]= max(dp[1][i-1]+ s[i] ,dp[0][i-1])

#(하나를 제외한 값 + 지금 값,  지금 값 제외 + 이때까지 더한 값)중에서 큰 값으로 변경해준다.


        else:
            dp[1][i]=dp[1][i-1]+ s[i] #양수면 그냥 더해준다.
    else:                   
        dp[1][i]= dp[0][i-1] #하나를 지웠으나 지금 값을 더했을때 음수가 되므로 지금 값을 지워주고 이때까지 더한 합으로 dp[1][i]를 정해준다.
s.sort()
if s[-1]<=0:#이 경우는 모든 수가 0이거나 음수일 경우이다.
    print(s[-1])#가장 작은 음수 값을 출력한다. 무조건 출력해야하기 때문에.
else:
    print(max(max(dp[0]),max(dp[1])))# 안 지워도 된다고했기에 지운dp and 안지운 dp중에서 가장 큰 값을 출력해준다.

 

주석 없는 버전

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

dp = [[0]*n for _ in range(2)]
for i in range(n):
    if dp[0][i-1]+ s[i]>=0:
        dp[0][i]=dp[0][i-1]+ s[i]

    if dp[1][i-1] +s[i]>=0:
        if s[i]<0:
            dp[1][i]= max(dp[1][i-1]+ s[i] ,dp[0][i-1]) 
        else:
            dp[1][i]=dp[1][i-1]+ s[i]
    else:                     
        dp[1][i]= dp[0][i-1]
s.sort()
if s[-1]<=0:
    print(s[-1])
else:
    print(max(max(dp[0]),max(dp[1])))

 

도움되셨으면 공감 한번씩 부탁드려요 로그인 필요 X