[백준] (Python) 11055번 - 가장 큰 증가하는 수열 (dp 풀이 방법)

기업 코딩테스트 연습으로 Swift가 아니라 Python으로 풀이했습니다 😅

 

⚫️ 문제

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

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

 

⚫️ 나의 풀이

이전에 보고와야할 것이 있다. '가장 큰 증가하는 수열'은 주어진 수열 속에서 '증가하는 부분 수열'을 찾는 문제다. LIS라고 불린다.

https://didu-story.tistory.com/236

[알고리즘] (Swift) 최강 증가 부분 수열 (LIS) 알고리즘 (DP, 동적계획법을 활용한 LIS)

내가 이렇게... 포스팅도 해놨다. 

기본적으로 LIS를 구하는 방식은 두가지다. '이분탐색'방식을 활용하는 것과 'dp'를 이용하는것! 두 개 모두 올바른 풀이이긴 하지만, 시간복잡도에 주의해야한다. dp는 for문을 이중으로 중첩해서 만들기 떄문에 O(N^2)의 시간 복잡도를 갖는다. 반면에, 이분탐색을 사용하면 O(nlogn)의 시간을 갖는다. 떄문에, 주어진 N에 대하여 시간복잡도를 고려해서 문제를 풀어야한다.

위 내 포스팅에는 dp를 이용해서 구하는 방식을 설명해뒀다. 그것을 기반으로 문제를 풀지만, 이번 문제는 조금 다르다. 이번문제에서는 가장 큰 증가하는 부분수열의 길이를 구하는게 아니라, 부분수열들 중에, 그 합이 가장 큰 것을 정답으로 골라야한다. 그렇다면, dp에 어떤것들을 넣어주어야할까?

내가 처음에 생각한 방식은 이거다.

dp[i] =  arr[i]를 기준으로 증가하는 부분수열의 최대 합

(예시)
arr = [1, 100, 2, 50] 이라치자.
dp[0] 에는 arr[0]이 마지막항이 된 Lis의 합을 넣는다. 즉, dp[0] = 1 이된다.
dp[1] 은, 100이고 이전 (i-1) 값보다 크므로, [1, 100]은 증가하는 부분수열이다. 그래서 dp[1]에는 두개의 합인 101을 넣는다.
dp[2]는 2이다. 앞과 같이 이전(i-1)값과 비교해보니, 100이 더 크므로 증가하는 부분수열이 될 수 없다. 하지만, arr[i-2]번째인 1보다 2가 크므로, [1,2]로 증가하는 부분수열을 만들 수 있다. 그럼 dp[2] 에는 1과 2를 더한 3을 넣어준다.
... (계속) 🔁

이렇게 dp에 값을 넣어줄 수 있을 것이다.

여기서 dp[2]를 구할 때, arr에서 0번째 부터 순회하면서 현재의 2보다 작은지 봐주고, 작다면 1까지의 합 (dp) + 현재의 2를 더해주는 식으로 가면 된다.  이해가 힘들다면 아래 그림을 보자.

 

위에서 말로 설명해둔 것을 이렇게 그리면서 생각했다. 마지막 i=2 가 되었을때, 조건과 이중 for문을 생각해낼 수 있었다.

 

⚫️ 정답 코드

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n

dp[0] = arr[0]

for i in range(0, n):
    dp[i] = arr[i]
    for j in range(0, i):
        if arr[j] < arr[i] and dp[i] < dp[j] + arr[i]:
            dp[i] = max(dp[i], dp[j]+arr[i])

print(max(dp))