알고리즘 - 동적계획법 (11054 가장 긴 바이토닉 부분수열)

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1 복사

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1 복사

7

---

문제 요약

한쪽으로만 커지는 부분수열이거나 감소하는 수열

아니면 삼각형처럼 증가하다 감소하는 수열 중 가장 긴 수열을 구하는 문제

 

 

접근 방식

증가나 감소에 대해서는 쉽게할 수 있었지만 증가하다 감소하는 수열에 대해 어떻게 해야할지 고민을 하다 중간을 기점으로 좌우가 감소하는 수열 즉, 중간을 기점으로 좌측은 증가, 우측은 감소 수열인 것을 통해 해결

 

for문을 통해 기준값을 돌려가며 양측을 구하려 했지만 중복되는 계산이 너무 많았기에 전부 구한 후 양 증가 감소 수열을 더하는 방식으로 진행

 

1. 실패

N = 10
 
l = [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]
 
up = [1]*N
down = [1]*N
 
for i in range(1,N):
    for j in range(i):
        if l[i] > l [j] and up[j]+1 > up[i]:
            up[i] = up[j]+1
        back = N-1
        if l[back-i] > l[back-j] and down[back-j]+1 > down[back-i]:
            down[back-i] = down[back-j]+1
 
max = 0
for i in range(N):
    if max < up[i]+down[i]:
        max = up[i]+down[i]
print(max-1)

원인 ; 2, [1,1]  일때 실패 => 최대값을 0으로 고정해서 발생

 

 

2. 성공

N = int(input())
 
l = list(map(int,input().split()))
 
up = [1]*N
down = [1]*N
 
for i in range(1,N):
    for j in range(i):
        if l[i] > l [j] and up[j]+1 > up[i]:
            up[i] = up[j]+1
        back = N-1
        if l[back-i] > l[back-j] and down[back-j]+1 > down[back-i]:
            down[back-i] = down[back-j]+1
 
max = up[0]+down[0]
for i in range(1,N):
    if max < up[i]+down[i]:
        max = up[i]+down[i]
print(max-1)

최대 초기값을 변경