백준/DP
[코딩테스트] #12. 백준 11055번: 가장 큰 증가 부분 수열
ydin
2021. 12. 24. 18:16
-문제: https://www.acmicpc.net/problem/11055
11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수
www.acmicpc.net
가장 긴 수열 갯수 구하는 문제와 같은패턴이라 쉽게 풀었던 문제. 스스로 풀었던 문제
-정답풀이:
n=int(input())
dp=list(map(int,input().split()))
m=[0]*n
m[0]=dp[0]
for i in range(1,n):
for j in range(i):
if dp[i]>dp[j] and m[i]<m[j]:
m[i]=m[j]
m[i]+=dp[i]
print(max(m))- 8번라인에 m[i]<m[j]과 9번라인 때문에 여러번 틀렸음.
- 값은 크더라도 그때까지 합이 j가 더 크면 원하는 답을 못함 따라서 m[i]< m[j] 만족하는지 확인해야함
- 9번은 이전 값을 누적해야하므로 필요한 과정
- 10번은 조건만족하는 수를 더해야하므로 있어야하는 라인이다
-틀린풀이:
