[Python] 백준 11055_ 가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055
이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.
1. DP정의
- dp: i번째까지 증가했을때 수열의 합의 최대값
- dp의 초기값은 입력받는 수열 A와 같도록 초기화 해준다
(예제)
5
10 90 20 80 100
(참고)
처음 d=a 라고 리스트를 복사하여 초기화를 했다가 오류가 발생했다.
파이썬의 리스트 변수는 리스트 객체를 직접 저장하고 있지 않다. 리스트 자체는 다른 곳에 저장되고 리스트의 참조값(리스트 객체의 위치)만 변수에 저장된다.
따라서 d=a 라고 하면 에 d리스트와 a리스트는 동일한 리스트 객체를 가리키게 된다.(얕은 복사)
그래서 위 코드와 같이, d 리스트의 값을 변경해주면 a 리스트이 값도 변경되어 결과값이 달라진다.
이를 해결할 수 있는 방법은 세가지가 있다.
1. 반복문을 이용한 복사: d = [i for i in a]
2. list()메소드 사용: d = list(a)
3. deepcopy() 메소드 사용:from copy import deepcopy d = deepcopy(a)
2. 점화식 찾기
d[i] = max(d[j]+a[i], d[i])
j = i앞의 index중 a[i]보다 a[j]가 작을 경우
3. 코드
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
#dp정의
d = [ i for i in a]
for i in range(1,n):
for j in range(i):
if a[j]<a[i]:
d[i] = max(d[j]+a[i],d[i])
print(max(d))
Author And Source
이 문제에 관하여([Python] 백준 11055_ 가장 큰 증가 부분 수열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soobin519/Python-백준-11055-가장-큰-증가-부분-수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)