13398. [Python]연속합 2

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 다이나믹 프로그래밍

 

3. 파이썬 코드

 

N = int(input())
num_list = list(map(int,input().split()))

# 문제에서 최소 한 개 이상의 수를 선택해야기 때문에 N이 1인 경우 예외처리 진행
if N == 1:
    print(num_list[0])
# N이 2개 이상인 경우
else:
    # 첫 누적합을 구할 리스트를 생성
    dp = [0] * N
    # 누적합을 구하기 위한 리스트는 첫 인덱스 값으로 선언
    dp[0] = num_list[0]
    # 1번 인덱스부터 N 까지 반복
    for i in range(1,N):
        # 현재 값에 i 인덱스 값을 초기값 선언
        dp[i] = num_list[i]
        # 그 자리에 이전값 + 현재 값, 현재 자리값을 비교해서 max 값 저장
        dp[i] = max(dp[i-1]+num_list[i], num_list[i])
    # 수를 1개를 제외한 경우리스트 생성
    answer = [0] * N
    # 이 값또한 0번 인덱스로 선언해줘야 함
    answer[0] = num_list[0]
    # 1개의 수를 제외한 경우를 반복문 진행하면서 체크
    for i in range(1,N):
        answer[i] = max(dp[i-1],answer[i-1]+num_list[i])
    # 두 리스트에서 max 값을 찾아서 출력
    print(max(max(dp),max(answer)))

 

4. 문제를 풀고난 후 생각

 

• 누적 합을 응용한 문제의 느낌으로 모든 값들에 대해서 이전값을 더한것과 현재 자리의 값을 비교해 큰값을 메모제이션 처리한 후 한 자리씩 그 값을 제외했을때 나올 수 있는 최적의 값을 찾는 문제였다.
• 초기 값 선언에 대해서 answer 리스트에 선언을 하지 않을 경우 값이 제대로 출력되지 않는 경우가 있기 때문에 모든 초기 0번 인덱스를 첫 값으로 선언해줘야 문제가 해결된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 다이나믹 프로그래밍