[백준][Python] 11055번 가장 큰 증가하는 부분 수열 - 코팩

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

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

풀이

누적합을 구하는 문제이고, 시간을 최소화하기 위해 다이내믹 프로그래밍을 사용할 예정이다.

다음과 같은 문제는 LIS알고리즘을 사용하여  풀 수 있다. 그러나 DP로 문제를 풀어보았습니다.

 

가장 큰 증가수열을 구하기 위해서 다음과 같이 고려된다.

1) 이전 누적합의 마지막 숫자보다 큰 숫자를 더해서 증가수열을 만든다.

2) 이전 누적합의 마지막 숫자보다 작아서 누적합을 만들 수 없는 경우, 해당 위치에서 새로 증가수열을 시작한다.

 

코드

# 11055번 가장 큰 증가하는 부분 수열
n = int(input())
nums = list(map(int, input().split()))
# 누적값 저장해줄 리스트.
dp = [0] * n

# 초기값 설정.
dp[0] = nums[0]

for i in range(1, n):
    for j in range(n):
        # 증가수열을 만족하는 경우들 중 최대값을 구해준다.
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], nums[i] + dp[j])
        # 증가수열을 만족하지 못한다면. 해당값에서 증가수열을
        # 시작한 값과 누적된 최댓값과 비교
        else:
            dp[i] = max(dp[i], nums[i])
print(max(dp))

출력결과