백준 문제 풀이 Python
[백준/Python] 11055번 가장 큰 증가 부분 수열
골슼
2022. 11. 29. 19:35
-문제
https://www.acmicpc.net/problem/11055
11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수
www.acmicpc.net
-가장 간단한 풀이 : 완전 탐색&DP
예제를 보면서 풀어봐요
저는 가장 직관적으로 생각할 수 있는 풀이에 아주 조금의 변형을 가미해 문제를 풀었어요.
먼저 arr 라는 이름의 리스트에 0과 주어진 수열을 저장해요.
arr=[0]
arr += list(map(int, input().split()))
arr = [0, 1, 100, 2, 50, 60, 3, 5, 6, 7, 8]
그리고 인덱스를 1부터 n까지 조사하며 dp 리스트에 각 인덱스의 값을 포함하는 증가 부분 수열 중 합이 최대인 경우를 저장했어요.
즉 dp[i] = 'arr[i]까지의 증가하는 부분 수열 중 합이 최대인 경우'라고 할 수 있어요.
dp 리스트를 채워나가기 위해서, 현재 주목하고 있는 인덱스의 arr 값보다 인덱스도 작고 값도 작은 원소들의 dp 값을 비교하고 그 최댓값을 현재 arr의 수와 더해주면 돼요.
n이 최대 1000까지 밖에 주어지지 않고, 인덱스 i에 대해 조사해야 할 경우도 i횟수이기에 수행해야 할 연산은 O(n^2)이에요. 그래서 주어진 시간은 가뿐히 통과할 수 있어요.
-가장 간단한 풀이의 소스코드
import sys
input = sys.stdin.readline
n = int(input())
arr=[0]
arr += list(map(int, input().split()))
dp = [0] * (n+1)
dp[1] = arr[1]
for i in range(2, n + 1):
temp = 0
for j in range(i, -1, -1):
if arr[j] < arr[i]:
if dp[j] > temp:
temp = dp[j]
dp[i] = temp + arr[i]
print(max(dp))