문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
11055번: 가장 큰 증가하는 부분 수열 문제보기
비슷한 문제 보기 : 11053번: 가장 긴 증가하는 부분 수열 문제보기
비슷한 문제 보기 : 1965번: 상자넣기 문제보기 문제보기
시간 제한: 1초
메모리 제한: 256MB
문제
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.
예제 입력 1
10
1 100 2 50 60 3 5 6 7 8
예제 출력 1
113
LIS는 Longest Increasing Subsequence 로써 최장증가부분수열 문제이다.
주어진 입력이
10
1 5 2 8 7 3 4 6 9 10
라고 하자
답은 1,2,3,4,6,9,10로 35이다.
가장 긴 수열을 찾으려면 자신의 숫자에서 이전 숫자들 다음 숫자이면 이전 숫자에 표기를 하고 현재 숫자에 다음 표기를 해주면 된다.
dp=[0]*11 을 만들어보자
1. 1에서 이전 숫자가 없으니
dp[1]은 1이다.
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2. 5에서 이전 숫자 1이 있으니
dp[5]=dp[1]+5=6이 되며 {1,5}는 증가하는 수열이다.
[0, 1, 0, 0, 0, 6, 0, 0, 0, 0, 0]
3. 2에서 이전 숫자들중에 자기보다 작은 수는 1이므로
dp[2]=dp[1]+2=3이 되며 {1,2}는 증가하는 수열이다.
[0, 1, 3, 0, 0, 6, 0, 0, 0, 0, 0]
4. 8에서 이전 숫자들 중에 자기보다 작은 수는 2 또는 5가 있다.
dp[8]=max(dp[:8])+8=14 이다. 즉, 자기 이전 숫자중 가장 연속인거({1,5})에 자기를 카운트하면된다.
[0, 1, 3, 0, 0, 6, 0, 0, 14, 0, 0]
5. 7도 마찬가지로 dp[7]=max(dp[:7])+7=13이다.
[0, 1, 3, 0, 0, 6, 0, 13, 14, 0, 0]
6. 3도 마찬가지로 dp[3]=max(dp[:3])+3=6이다.
[0, 1, 3, 6, 0, 6, 13, 0, 14, 0, 0]
반복하다가....
마지막은
dp[10]=max(dp[:10])+10=35가 된다.
[0, 1, 3, 6, 10, 6, 16, 13, 14, 25, 35]
즉, 자기 번호에서 이전 번호 보다 큼을 표기하면된다.
정답 코드
import sys
# sys.stdin=open('input.txt','r')
input=sys.stdin.readline
if __name__=="__main__":
N=int(input())
infos=list(map(int, input().split()))
dp=[0]*1001
for i in infos:
dp[i]=max(dp[:i])+i
# print(dp)
print(max(dp))
DP, 다이나믹 프로그래밍은 점화식!
