백준 11055번 가장 큰 증가하는 부분 수열 (Python)

문제

문제
수열 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의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

• 예제 입력

10
1 100 2 50 60 3 5 6 7 8

• 예제 출력

113

정답 코드

import sys

n = int(sys.stdin.readline().strip())
array = list(map(int, sys.stdin.readline().strip().split()))
array.insert(0, 0)  ## dp 테이블과의 인덱스를 맞추기 위해서 (합이니까 0을 추가하는 것은 괜찮음)

## 그 증가수열의 합을 저장하는 dp 테이블 정의
hap_dp = [0] * 1001
hap_dp[0] = 0

## O(n^2) 알고리즘으로 몇개가 증가하고 있는지 확인하고 그 합을 저장하는 DP 테이블 정의하기
for idx, value in enumerate(array[1:], start=1):
  hap_dp[idx] = value
  max_hap = value
  # print(f"**{value}**")

  for iidx, previous_value in enumerate(array[:idx]):
    if previous_value < value:
      max_hap = max(max_hap, hap_dp[iidx] + value)
      # print(max_hap)
      hap_dp[idx] = max_hap
  # print()

# print(array)
# print(hap_dp[:len(array)])
print(max(hap_dp))

문제 해결 접근

증가하는 부분 수열

• 먼저 문제 이해가 잘 안 가서 '증가하는 부분 수열' 이 무엇인지를 확인했다.
• 최장 증가 부분 수열 나무위키 를 통해서 "어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있고, 이 떄 만들어진 부분 수열 중 오름차순으로 정렬된 수열" 이 증가하는 부분 수열이라는 것을 이해할 수 있었다.
• LIS (longest increasing sequence) 를 구할 때 dp table을 정의한 다음에, 거기에 자기 현재 인덱스보다 앞에 있는 수들 중 작은 값의 수를 넣는 방식을 확인할 수 있었다.
  

문제 해결 아이디어

• 증가 부분 수열이 뭐고 어떻게 구하는지 확인을 했으니, 이제 가장 큰 합을 어떻게 정의하여 넣을까 고민하는 과정이 있었다.
• max_hap을 정의한 다음에 그 값을 hap_dp에 넣어주어서 이를 활용하는 것이 key idea
• 나보다 앞에 있는 값이 나보다 작은 경우, (1) 여태까지의 max_hap과 (2) 새로운 위치에서의 합을 비교하여 큰 값을 max_hap으로 두어 업데이트 한다.
• 이렇게 될 경우 hap_dp는 매 스텝마다 max_hap을 계속 저장하게 되므로, 이를 쌓아서 활용하면 된다.
• 이를 출력해보면 아래와 같다. (정답 코드에서 주석처리한 print를 해제해서 확인하면 된다!)
  

반례 찾기

• 백준 문제를 풀다보면 테스트 케이스에는 정답값이 잘 나오기 때문에 어떤 것이 잘못된 것인지 잘 모를 때가 있다.
• 그럴 때는 지금 내 로직이 무엇이 잘못되었는지 확인해줄 수 있는 반례를 찾는 것이 필요한데 이럴 경우 질문게시판에 들어가서 확인하다 보면 답을 좀 더 잘 찾을 수 있다.
• 이번 문제에서 특히 도움된 반례는 백준 질문 게시판의 이 글 이다.
• 나의 경우 5 1 2 3 10 수열과 같이, 10보다 앞에 있는 숫자들이 다 작지만, 1+2+3=6 과 5 둘 중 하나만 취사선택해서 합해야 한다는 아이디어를 깨달은 것이 도움이 되었다.