백준(baekjoon) 11054번: 가장 긴 바이토닉 부분 수열(골드 4, 파이썬 PYTHON)

문제

수열 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

https://www.acmicpc.net/problem/11054

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

  

import sys

N=int(sys.stdin.readline())
Ai=list(map(int,sys.stdin.readline().split()))
dp_increase=[0]*N
dp_decrease=[0]*N
max=-1

for x in range(N):
  for y in range(x):
    if(Ai[x]>Ai[y] and dp_increase[x]<dp_increase[y]):
      dp_increase[x]=dp_increase[y]
  dp_increase[x]+=1

for x in range(N-1,-1,-1):
  for y in range(N-1,x,-1):
    if(Ai[x]>Ai[y] and dp_decrease[x]<dp_decrease[y]):
      dp_decrease[x]=dp_decrease[y]
  dp_decrease[x]+=1

for x in range(N):
  if(max==-1 or dp_increase[x]+dp_decrease[x]-1>max):
    max=dp_increase[x]+dp_decrease[x]-1

print(max)

 

※ 동적 계획법 1

 

 

● 먼저 수열 A의 크기 N을 입력받은 후, 이후의 입력을 Ai 배열에 차례대로 넣어준다. 그리고 Ai 배열에서 각 요소를 포함하는 가장 긴 증가하는 부분 수열의 길이를 저장할 초기값이 0이고 크기가 N인 dp_increase 배열과 Ai 배열에서 각 요소를 포함하는 가장 긴 감소하는 부분 수열의 길이를 저장할 초기값이 0이고 크기가 N인 dp_decrease 배열을 정의해준다. 마지막으로 초기값이 -1인 max 변수를 선언해준다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

각 요소를 포함하는 가장 긴 증가하는 부분수열의 길이 구하기(dp_increase)

->

 

● 변수 x는 0부터 N-1까지, 변수 y는 0부터 x-1 까지 돈다.(y는 인덱스 x 인 Ai 원소보다 앞에있는 원소들을 접근하게 된다.)

만약 Ai[x] 가 Ai[y] 보다 크고( Ai[x] 가 더 크다면, Ai[y] 를 포함하는 가장 긴 증가하는 수열 뒤에 Ai[x]를 이어붙여도 증가하는 수열을 만족하게 된다.), dp_increase[x] 보다 dp_increase[y] 가 더 크면, dp_increase[x] 에 dp_increase[y] 의 값을 넣어준다.(이전에 고려하였던 상황보다 현재 Ai[y] 를 포함하는 가장 긴 증가하는 수열 뒤에 Ai[x] 를 붙이는 것이 더 길다면, dp_increase[x] 에 dp_increase[y]의 값 넣어줌.)

 

● y for문이 다 돌면, 현재 dp_increase[x] 에는 Ai[x] 가 뒤에 들어가도 증가하는 수열을 만족하는 증가하는 수열 중 가장 긴 수열의 길이가 들어가 있다. 이 수열에 Ai[x] 를 뒤에 붙이면 길이가 1 증가하므로 dp_increase[x]+=1 연산을 해준다.

 

각 요소를 포함하는 가장 긴 증가하는 부분수열의 길이 구하기(dp_decrease)

->

 

● 변수 x는 N-1부터 0까지, 변수 y는 N-1부터 x+1까지 돈다.(y는 인덱스 x 인 Ai 원소보다 뒤에있는 원소들을 접근하게 된다.)

만약 Ai[x] 가 Ai[y] 보다 크고( Ai[x] 가 더 크다면, Ai[y] 를 포함하는 가장 긴 감소하는 수열 앞에 Ai[x]를 이어붙여도 감소하는 수열을 만족하게 된다.), dp_decrease[x] 보다 dp_decrease[y] 가 더 크면, dp_decrease[x] 에 dp_decrease[y] 의 값을 넣어준다.(이전에 고려하였던 상황보다 현재 Ai[y] 를 포함하는 가장 긴 감소하는 수열 앞에 Ai[x] 를 붙이는 것이 더 길다면, dp_decrease[x] 에 dp_decrease[y]의 값 넣어줌.)

 

● y for문이 다 돌면, 현재 dp_decrease[x] 에는 Ai[x] 가 앞에 들어가도 감소하는 수열을 만족하는 감소하는 수열 중 가장 긴 수열의 길이가 들어가 있다. 이 수열에 Ai[x] 를 앞에 붙이면 길이가 1 증가하므로 dp_decrease[x]+=1 연산을 해준다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

● 새로운 for 문에서 x는 0부터 N-1 까지 돈다. dp_increase[x] + dp_decrease[x] -1 중 가장 큰 값이 가장 긴 바이토닉 부분 수열의 길이가 된다. (Ai[x]를 포함하는 가장 긴 증가하는 수열의 길이 + Ai[x]를 포함하는 가장 긴 감소하는 수열의 길이, Ai[x] 가 중복해서 계산되므로 1을 빼줘야 함!!) max 값이 -1 이거나 현재 max 값보다 dp_increase[x] + dp_decrease[x] -1 의 값이 더 크다면 max 를 이 값으로 갱신해준다. 모든 연산이 끝난후 max 에 들어가있는 값을 출력해주면 답을 구할 수 있다.

 

 

 

 

결과

 

 

♣ 참고: 가장 긴 증가하는 부분수열(LCS)

-> https://doyourbestcode.tistory.com/69

백준(baekjoon) 11053번: 가장 긴 증가하는 부분 수열(실버 2, 파이썬 PYTHON) - 동적 계획법 1