BOJ [Silver II] 가장 큰 증가 부분 수열 - 11055

문제 링크

분류

다이나믹 프로그래밍(dp)

문제 설명

수열 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)

10
1 100 2 50 60 3 5 6 7 8

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다

113

아이디어

• 11053이랑 비슷하게 풀었음

• 이번에는 수열의 길이가 아니라 합이기 때문에, +1로 개수를 하나 더해주던 것에서 +수열의 값으로 합을 업데이트 해줌

• 반례 하나 해결한다고 조금 고민이 필요했음

내 코드1: 틀렸습니다

n = int(input())
a = list(map(int, input().split()))
d = [0] * 1001
d[0] = a[0]

for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            d[i] = max(d[i], d[j] + a[i])
print(max(d))

• d[0] = a[0] 가 문제였음

• d[0]을 a[0]으로 초기화해주지 않으면 i를 range(n)으로 돌려도, 인덱스 0에서는 0보다 작은 j가 없기 때문에 a[0]을 더하지 않게 됨

• 입력 예시 넣어봤을 때 계속 a[0] 값이 더해지지 않은 채로 나와서 별 생각 없이 인덱스 0에 대해서만 초기화해줬었음!

반례

3
2 1 2

정답: 3
출력: 2

• a[1]이 a[0]보다 작기 때문에 if문 실행이 안 되고 다음 인덱스로 넘어가면서 d[1]에 a[1]이 들어가지 않게 됨

  → a[2]가 a[1]보다 크지만, d[1]에 a[1]이 아닌 처음 초기화 상태 0이 들어가 있어서 a[1] + a[2]가 아니라 0 + a[2]가 되어버림

• 그래서 뭔가 인덱스를 구분할 변수가 필요할까? 하다가

  d[0]을 a[0]으로 초기화해준 것처럼, 문제에서 원하는 게 "합"이니까 기본적으로 자기 자신은 가지고 있어야 하겠구나 생각함!

내 코드2: 맞았습니다

n = int(input())
a = list(map(int, input().split()))
d = [0] * 1001

for i in range(n):
    d[i] = a[i]

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            d[i] = max(d[i], d[j] + a[i])
            
print(max(d))

• d를 크게 잡아놨으니까 그냥 for 문으로 넣어줌

• 크게 안 잡아준다면 그냥 d = a[:] or d = [x for x in a] or d = a.copy()이런 식으로 가능

  대신 d = a 는 하지 말기 .. ~ 냅다 참조해버리니까

• 복사 안 해줄 거면 else문에 d[i] = max(d[i], a[i])를 해줘도 됨!
  
  

다른 사람 코드

input()
dp = [0] * 1001
for i in map(int, input().split()):
    dp[i] = max(dp[:i]) + i

print(max(dp))

• 근데 이렇게 야무진 코드가~~..

• 수열의 원소로 들어올 수 있는 최댓값이 1000이니까 그거보다 dp 리스트를 크게 잡아주고, 인덱스가 수열의 값 자체가 되는 거

8
10 2 5 6 3 5 6 7 8

일 때

이렇게 됩니다요