문제 설명
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
문제 분석과정
연속합의 최대는 어떻게 만들어질까?
연속합은 어떤인덱스 x 에서 시작해서 어떤인덱스 y에서 종료된다.
종료되는 y 인덱스 관점에서 살펴보자
dpTable 을 생성하고 dpTable에 의미를 부여하자(정의하자)
dpTable은 종료되는 인덱스까지의 연속합의 맥스값이다.
정답은 max(dpTable)이 될 것이다.
테이블을 만들기위해 초기값을 살펴보자
(인덱스가 헷갈릴 수 있으므로 배열으크기를 n+1로 초기화해준다. )
주어진 배열이 0 10 -4 3 1 5 6 -35 12 21 -1 라고 할때
dp[1]은 무엇일까?
dp[1]은 10이다.
dp[2]는? dp[2]은 10 -4 이다.
dp[3]는? dp[3]은 10 -4 +3 이다.
dp[4]는? dp[4]은 10 -4 +3 +1이다.
dp[5]는? dp[5]은 10 -4 +3 +1 +5이다.
dp[6]는? dp[6]은 (10 -4 +3 +1 +5+ 6) = 21이다.
dp[7]는? dp[7]은 (10 -4 +3 +1 +5+ 6 -35) = -14이다.
dp[8]는? dp[8]은 max((10 -4 +3 +1 +5+ 6 -35),12) = 12이다.
dp[k] = max(dp[k-1]+arr[k], arr[k]) 위 케이스를 통해서 점화식을 생성할 수 있다.
dp[9] = max(dp[8]=12+21, 21) = 33
dp[10] = max (dp[9]-1, -1) = 32
여기서 주의사항이 한가지가 있다.
바로 초기화값인데, 인덱스를 헷갈리지않게 하기위해서 추가하는데이터값에 주의해야한다.
보통이런경우 통상적으로 0을 추가하는데 해당문제에서 0으로 추가하는 경우 통과하지못하는 테스트 케이스가 나온다.
어떤 케이스 일까 ? 바로 모든 수가 음수인 경우이다.
-3 -4 -7 -3
다음과 같은 테스트케이스가 들어왔다고 생각해보자.
그럼 arr는 arr = [0,-3,-4,-7,-3]이 될 테고
dp = [0,-3,-4,-7,-3]이 될것이다. 따라서 max(dp) = 0이되고 원하는 답인 -3 이 출력되지않게된다.
그럼 방지하기위해서 어떻게해야할까?
입력데이터를 확인해보자, 입력데이터는 "-1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다." 라고 주어져있다.
따라서 -1001 보다 같거나 작은수는 절대로 나올 수 없다 . 그럼 이조건을 활용해 인덱스 0번째 데이터를 -1001로 초기화하면
모든 수가 음수인 경우를 문제없이 해결할 수 있다.
소스코드
import math
n = int(input())
arr = [0]+list(map(int,input().split()))
dp = [-1001]*(n+1)
# 연속합의 최대는 어떻게 만들어질까?
# sol
# 연속합은 어떤인덱스 x 에서 시작해서 어떤인덱스 y에서 종료된다.
# 종료되는 y 인덱스 관점에서 살펴보자
# dpTable 을 생성하고 dpTable에 의미를 부여하자(정의하자)
# dpTable은 종료되는 인덱스까지의 연속합의 맥스값이다.
# 정답은 max(dpTable)이 될 것이다.
# 테이블을 만들기위해 초기값을 살펴보자
# (인덱스가 헷갈릴 수 있으므로 배열으크기를 n+1로 초기화해준다. )
# 주어진 배열이 0 10 -4 3 1 5 6 -35 12 21 -1 라고 할때
# dp[1]은 무엇일까? dp[1]은 10이다.
# dp[2]는? dp[2]은 10 -4 이다.
# dp[3]는? dp[3]은 10 -4 +3 이다.
# dp[4]는? dp[4]은 10 -4 +3 +1이다.
# dp[5]는? dp[5]은 10 -4 +3 +1 +5이다.
# dp[6]는? dp[6]은 (10 -4 +3 +1 +5+ 6) = 21이다.
# dp[7]는? dp[7]은 (10 -4 +3 +1 +5+ 6 -35) = -14이다.
# dp[8]는? dp[8]은 max((10 -4 +3 +1 +5+ 6 -35),12) = 12이다.
# dp[k] = max(dp[k-1]+arr[k], arr[k]) 위 케이스를 통해서 점화식을 생성할 수 있다.
# dp[9] = max(dp[8]=12+21, 21) = 33
# dp[10] = max (dp[9]-1, -1) = 32
# 여기서 주의사항이 한가지가 있다.
# 바로 초기화값인데, 인덱스를 헷갈리지않게 하기위해서 추가하는데이터값에 주의해야한다.
# 보통이런경우 통상적으로 0을 추가하는데 해당문제에서 0으로 추가하는 경우 통과하지못하는 테스트 케이스가 나온다.
# 어떤 케이스 일까 ? 바로 모든 수가 음수인 경우이다.
# -3 -4 -7 -3
# 다음과 같은 테스트케이스가 들어왔다고 생각해보자.
# 그럼 arr는 arr = [0,-3,-4,-7,-3]이 될 테고
# dp = [0,-3,-4,-7,-3]이 될것이다. 따라서 max(dp) = 0이되고 원하는 답인 -3 이 출력되지않게된다.
# 그럼 방지하기위해서 어떻게해야할까?
# 입력데이터를 확인해보자, 입력데이터는 "-1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다." 라고 주어져있다.
# 따라서 -1001 보다 같거나 작은수는 절대로 나올 수 없다 . 그럼 이조건을 활용해 인덱스 0번째 데이터를 -1001로 초기화하면
# 모든 수가 음수인 경우를 문제없이 해결할 수 있다.
for i in range (1,n+1):
dp[i] = max(dp[i-1]+arr[i],arr[i])
print(max(dp))
분류
다이나믹 프로그래밍(dp)
오류나 질문에 대한 문의 댓글로 남겨주세요!
