[python] 동적 프로그래밍_백준 문제풀이(11053번, 11054번)

수열 문제, DP로 풀어보자!

11053번 - 가장 긴 증가하는 부분 수열

문제 설명

이 문제는 생각보다 문제를 이해하는 데에 시간 소모가 컸다.
역시 문제를 처음 접했을 때, 문제와 입력 조건, 출력을 잘 읽어보는 것이 중요하다는 걸 또 한번 느낄 수 있었다.

수열이 주어졌을 때, 증가하는 숫자의 수열 (연속 조건 x) 길이 중 가장 긴 길이를 구하는 것이다.

테스트 케이스가 간단한 입력만 나와있어서 그거만 보고 풀었다가는 산으로 갈 수 있다.
<101, 1, 2, 3, 4, 102, 5, 6, 103>, <3,1,2,4,5,3,4> 와 같은 케이스를 고려해야 하기 때문이다!

처음 드는 DP의 사고방식은 각 인덱스마다 그 값으로 끝나는 증가하는 수열의 길이를 저장하는 것이었다.
그렇다면 그 다음 값이 나왔을 때, 자신보다 앞에 있고 작은 값들의 dp 값 중 가장 큰 값 + 1을 저장하면 되지 않을까?

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split(' ')))
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))  

11054번 - 가장 긴 바이토닉 부분 수열

이 문제는 앞에서 푼 문제와 유사하지만 조건이 증가가 아닌, 바이토닉이라는 응용이 더해졌다.
바이토닉이란 증가하다가 최고값 뒤로는 감소하는 것이다.

그래서 앞에서 뒤로 했던 동작을 뒤에서 앞으로 동작하며 각각 다른 배열로 저장해놓자는 생각을 해보았다.
그 후 각 인덱스의 합을 더하면 앞에서 증가한 수, 뒤로는 감소한 수를 알 수 있다!
다만 여기서 그 값이 중복으로 카운트 되기 때문에 1을 빼주어야 한다.

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split(' ')))
dp_1 = [1] * n
for i in range(1, n):
    for j in range(0, i):
        if arr[j] < arr[i]:
            dp_1[i] = max(dp_1[i], dp_1[j] + 1)

dp_2 = [1] * n
for i in range(n-2, -1, -1):
    for j in range(n-1, i, -1):
        if arr[j] < arr[i]:
            dp_2[i] = max(dp_2[i], dp_2[j] + 1)
dp = []
for i in range(n):
    dp.append(dp_1[i]+dp_2[i])

print(max(dp)-1)

오늘은 어렵게만 느껴졌던 문제를 dp로 풀어내니 뿌듯하고 재밌었다!