[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

2. 풀이과정

해당 문제는 부분 수열 중 가장 긴 바이토닉 수열의 길이를 찾는 문제이다.

해당 문제는 이전의 백준 11053번 : 가장 긴 증가하는 부분 수열 문제를 응용하면 쉽게 해결할 수 있는 문제이다.

DP 알고리즘을 활용하여 처음부터 끝까지 부분 수열 중 앞의 수보다 크면 1씩 해당 위치의 값을 증가하면서 각 위치별로 증가하는 부분 수열의 길이를 알 수 있다.

이를 거꾸로 생각하면 가장 긴 감소하는 부분 수열을 찾을 수 있다.

두 부분 수열의 길이를 위치별로 더해 해당 값 중 최댓값을 구하고 해당 위치의 원소가 2번 중복되므로 1을 빼주면 가장 긴 바이토닉 수열의 길이를 구할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 수열의 크기를 입력받는다. N = int(sys.stdin.readline())
3. 수열의 각 원소를 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
4. 각 원소 위치별 증가하는 부분 수열의 길이를 저장할 리스트를 생성하고 초기에 각 원소의 길이인 1로 초기화해 준다. dp1 = list(1 for _ in range(N))
5. 두 번째 원소의 위치인 1부터 시작하여 마지막 원소까지 반복하고 for i in range(1, N)
6. 해당 위치 이후 원소를 하나씩 불러오며 for j in range(i)
7. 만약 비교 기준 원소가 비교하는 원소보다 크면 if (A[j] < A[i])
8. 해당 위치에 비교하는 원소의 위치 값 + 1과 비교 기준 원소의 위치 값 중 최댓값을 저장한다. dp1[i] = max(dp1[j] + 1, dp1[i])
9. 감소하는 부분 수열의 길이를 저장하기 위해 수열의 원소를 거꾸로 뒤집어 준다. A.reverse()
10. 각 원소 위치별 감소하는 부분 수열의 길이를 저장할 리스트를 생성하고 초기에 각 원소의 길이인 1로 초기화해 준다. dp2 = list(1 for _ in range(N))
11. 두 번째 원소의 위치인 1부터 시작하여 마지막 원소까지 반복하고 for i in range(1, N)
12. 해당 위치 이후 원소를 하나씩 불러오며 for j in range(i)
13. 만약 비교 기준 원소가 비교하는 원소보다 크면 if (A[j] < A[i])
14. 해당 위치에 비교하는 원소의 위치 값 + 1과 비교 기준 원소의 위치 값 중 최댓값을 저장한다. dp2[i] = max(dp2[j] + 1, dp2[i])
15. 감소하는 부분 수열의 길이를 저장한 리스트를 다시 거꾸로 뒤집어준다. dp2.reverse()
16. 최종 바이토닉 수열의 길이를 저장할 리스트를 생성한다. dp = [0] * N
17. 각 워치별로 반복하며 for i in range(N)
18. 해당 위치에서의 증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이를 더해 저장한다. dp[i] = dp1[i] + dp2[i]
19. 최종으로 최댓값에 해당 위치의 원소가 2번 반복되는 부분 수열이므로 길이에서 1을 빼주면 가장 긴 바이토닉 수열의 길이가 된다. print(max(dp) - 1)

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

dp1 = list(1 for _ in range(N))
for i in range(1, N):
    for j in range(i):
        if (A[j] < A[i]):
            dp1[i] = max(dp1[j] + 1, dp1[i])

A.reverse()
dp2 = list(1 for _ in range(N))
for i in range(1, N):
    for j in range(i):
        if (A[j] < A[i]):
            dp2[i] = max(dp2[j] + 1, dp2[i])

dp2.reverse()

dp = [0] * N
for i in range(N):
    dp[i] = dp1[i] + dp2[i]

print(max(dp) - 1)