[백준] 가장 긴 바이토닉 - python (11054번)

풀이 전략

가능한 모든 경우의 수를 생각하는 것은 무리라고 생각이 들었습니다. 수열 길이가 최대 1000이기 때문입니다. 따라서 다이나믹 프로그래밍 (DP)로 풀어야 겠다고 생각하였습니다.

DP 로직의 포인트는 바이토닉 수열에서 꺽이는 점, 즉 바이토닉 수열이 증가하다 감소하는 형태이니 수열의 값들 마다 해당 값이 꺽이는 점 일때 바이토닉 수열의 최대 길이는 몇이 되는지를 확인하는 로직으로 코드를 작성하였습니당

풀이 과정

1. 증가 길이 체크

수열의 값들을 하나하나 봅니다. 해당 값보다 앞에 있는 값들과 크기를 비교하며 더 크다면 증가 수열의 길이를 + 1 해주고 이때 다이나이믹 프로그래밍 기법이 적용됩니다.

문제의 테스트 케이스를 예로 들어

board = [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]

A = len(board)
increasing = [1] * A

for i in range(1, A):
    for j in range(i):
        if board[i] > board[j] and increasing[i] < increasing[j] + 1:
            increasing[i] = increasing[j] + 1

일 때 1번째 값인 5부터 확인을 하게 됩니다. 5는 0번째 값인 1보다 크기가 크고 increasing의 값도 동일하기 때문에 increaing의 1번째 값을 2로 바꿔줍니다.

이와 같은 방법을 적용하면 해당 인덱스 까지 최대로 길게 만들 수 있는 증가 수열의 길이가 increasing 리스테 담기게 됩니다.

increasing리스트는

increasing -> [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]

의 값을 가지게 됩니다.

2. 감소 길이 체크

동일한 방법으로 감소하는 부분 수열의 최대 길이를 수열의 각 인덱스 별로 저장합니다. 이때 증가 길이를 체크할 때는 0번째 부터 자신 전까지의 값을 비교했지만 감소 길이를 체크할 때는 자신 이후의 값부터 -1번째 값까지 체크해야 됩니다.

마찬가지 방법으로 decreasing리스트를 만들면

for i in range(A - 2, -1, -1):
    for j in range(A - 1, i, -1):
        if board[i] > board[j] and decreasing[i] < decreasing[j] + 1:
            decreasing[i] = decreasing[j] + 1

이렇게 만들 수 있고 결과는

decreasing -> [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

이 됩니다.

3. 길이 더해보기

이제 증가하는 길이와 감소하는 길이를 더해서 최댓값을 찾아주기만 하면 됩니다.

예를 들어

1번 인덱스, 즉 5를 꺽이는 점이라고 한다면 앞부분, 증가하는 부분의 최대 길이는 increasing의 1번 인덱스 '2'가 되고 감소하는 부분의 최대 길이는 decreasing의 1번 인덱스 '5'가 됩니다. 이때 1번 인덱스가 2번 세지는 형태이므로 실제 총 바이토닉 수열의 길이는 2 + 5 - 1인 6이 됩니다.

7번 인덱스인 5를 꺽이는 점으로 잡아보겠습니다. increasing의 7번 인덱스인 5, decreasing의 7번 인덱스인 3이므로 7번 인덱스를 꺽이는 점으로 잡았을 때의 바이토닉 수열의 최대 길이는 5 + 3 - 1인 7이 되고 이것이 정답이 됩니다.

import sys

input = sys.stdin.readline

A = int(input())
board = list(map(int, input().split()))

increasing = [1] * A
decreasing = [1] * A

for i in range(1, A):
    for j in range(i):
        if board[i] > board[j] and increasing[i] < increasing[j] + 1:
            increasing[i] = increasing[j] + 1

for i in range(A - 2, -1, -1):
    for j in range(A - 1, i, -1):
        if board[i] > board[j] and decreasing[i] < decreasing[j] + 1:
            decreasing[i] = decreasing[j] + 1

M = 0
for i in range(A):
    length = increasing[i] + decreasing[i] - 1
    if length > M:
        M = length

print(M)