[백준 2024/10/04] 11055번 가장 큰 증가하는 부분 수열

1. 문제

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

 

2. 접근 방법

처음에는 위와 같이 구상하였다.

현재 idx에서 이전 idx를 비교를 하면서 0번 idx까지 내려간다. 만약 값이 현재 idx value 보다 작다면, max(inc[idx], inc[idx] + arr[i])

를 진행해준다. max를 이용하는 이유는 더 앞에서 현재 값보다 더 큰 값을 지니고 있는 증가하는 수열이 있을 수 있기 때문이다.

 

처음에는 현재 idx보다 작은 값을 찾으면 바로 값을 더해주고 break를 해주었다.

하지만

[10, 22, 9, 33, 21, 50, 41, 60, 80]
[1, 2, 1, 2 ### 3 이 들어가야 함.

증가하는 수열의 길이를 파악하는 과정을 보면, 만약, 현재 idx보다 작을 시, break를 한다면 33의 경우 2의 값을 지니게 된다.

하지만, 더 앞을 탐색하면, 10 - 22 - 33 으로 3의 값을 가질 수 있다. 따라서 0번 idx까지 탐색을 해주어야 한다.

 

3. 코드

import copy


def max_val(arr, inc_a, n):
    for i in range(1, n, 1):
        for j in range(i-1, -1, -1):
            if arr[j] < arr[i]:
                inc_a[i] = max(inc_a[i], inc_a[j] + arr[i])
                
    return max(inc_a)


if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    inc_a = copy.deepcopy(arr)
    print(max_val(arr, inc_a, n))