[백준/python][DP] 11055번 가장 큰 증가하는 부분 수열

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

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

# 문제

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

---

# 코드

2가지 코드가 있다.

<코드 1>

import sys
r_line = sys.stdin.readline

n = int(r_line())
arr = list(map(int, r_line().split()))
dp = arr[:]

# 비즈니스 로직
for i in range(1, n): # i
    for j in range(i):
        if arr[i] > arr[j]: # 현재숫자가 더 작다면 
            dp[i] = max(dp[i], dp[j]+arr[i])

print(max(dp))

 

<코드 2>

import sys
r_line = sys.stdin.readline
n = int(r_line())
arr = list(map(int, r_line().split()))

dp = [0]*1001
for i in arr:
    # 자기값을 더하는데 가장큰거를 넣는다.
    dp[i] = max(dp[:i]) + i

print(dp)
print(max(dp))

 

1번 풀이 속도: 164ms

2번 풀이 속도: 48ms

2번풀이가 4배 정도 빨랐다.

---

# 풀이

1번풀이는  가장 긴 증가하는 부분 수열 (백준 11053번)과 같은 방식으로 풀었다.

참고: https://www.acmicpc.net/problem/11053

1번 풀이

 

dp[i]: arr[i]를 마지막 값으로 가지는 증가수열이다.

따라서 for문을 검사하면서 나보다 작은 값이 있다면 추가할 수 있는 거니까 max로 검사를 한다.

작은 값 + 현재 나의 값 (dp[j] + arr[i])

가 지금 값보다 크다면 (dp[j] + arr[i])이 더 큰 증가수열이다.

따라서 dp[i]를 더 큰 증가수열로 업데이트 해준다.

 

2번풀이는 백준에서 빨리 푼 파이썬3 풀이를 참고하였다.

예시를 프린트해보면 이런 콘솔창이 나온다.

따라서 나보다 작은 값의 해당하는 dp[:i] 값들 중 가장 큰 값을 찾아서 더한다.

자기 자리는 해당 값을 의미하므로 

1번과 달리 if비교문 필요 없이 자기 자리보다 하위 값들 중 가장 큰 값을 뽑아서 자신의 값과 더한다.

이러면 지금까지 나온 값 중에서 가장 길이가 긴 증가수열에 가장 큰 값(나 자신)을 자신의 idx에 넣게 된다.

따라서 그중에서 max를 뽑으면 된다.

 

 

 

둘 다 O(N^2)의 시간복잡도를 가지긴 한다.

파이썬 공식문서에서도 MAX는 O(n) 시간복잡도라 나와있기에 시간복잡도는 같다.

 

하지만 n이 작은 점 1000 그리고 1번은 배열의 인덱스개수가 작을 때 이득을 볼 수 있고

2번은 값의 따라 dp배열의 크기를 할당해야 하기에 1000밖에 안 되는 크기이기 때문에 

여기서 시간적으로 이득을 많이 본 거 같다.

 

크기 n값이 더욱 커진다면 1번이 시간복잡도적으로 이득일 것이다.

그럼에도 2번은 if검사를 하지 않는 점에서 배열의 개수가 커져도 max에서 끝나기에 

 

갯수가 많을 때는 2번이 이득.

값이 커지면 1번이 이득이다. 

 

정리

value 커지면 1번이 이득.

n(개수)가 커지면 2번이 이득.