가장 큰 증가 부분 수열[백준 11055] - python

문제 이미지

 

import sys
input = sys.stdin.readline

def BOJ11055() :
  N = int(input())
  array = list(map(int, input().split()))
  memo = list(array)
  
  for index in range(1, len(array)) :
    max_point = 0
    for j in range(index) :
      if array[j] < array[index] and max_point < memo[j] + array[index] :
        max_point = memo[j] + array[index]
    memo[index] = max(memo[index], max_point)

  print(max(memo))

BOJ11055()

 

접근 방법

0. 다이나믹 프로그래밍 방법으로 접근하였다.

1. 각 인덱스 마다 이전의 값들과 비교하여 부분수열의 합의 최대값을 업데이트 해주어야 한다.

2. 현재 자신 인덱스의 누적 값과 자기보다 작은 값의 인덱스의 누적값을 비교해주어서 업데이트 해주어야 한다

 

 

장애물이 였던것

0. 너무 복잡하게 생각해서 접근하였다.

1. 각 인덱스의 값들은 현재 자신이 가지고 있는 값이 최솟값 이다.

2. 1에 근거하여 memo의 값을 0으로 무자비하게 초기화 하면 안된다

3. 이진 탐색기법을 적용하여 문제를 풀려 시도 했었으나 실패했다. => 이진 탐색을 사용하면 값이 적절히 업데이트 되지가 않는다(적절히 업데이트 되는걸로 코드 새로 짜야한다.)

 

 

https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열