백준 11054(가장 긴 바이토닉 부분 수열) - Python(파이썬),Java(자바) - DP

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

예제 풀이

가장 긴 바이토닉 부분 수열이 되기 위해서는 1 2 3 4 5 2 1 이 경우가 가장 기므로 출력으로 7이 나오게된다.

이걸 dp로 해석하면

증가하는지 dp로 확인하기

1) dp[1] = 5 전 수열 증가하는지 확인

결과

1	5	2	1	4	3	4	5	2	1
1	2	1	1	1	1	1	1	1	1

2) dp[2] = 2 전 수열 증가하는 지 확인

1	5	2	1	4	3	4	5	2	1
1	2	2	1	1	1	1	1	1	1

2) dp[3] = 1 전 수열 증가하는 지 확인

1	5	2	1	4	3	4	5	2	1
1	2	2	3	1	1	1	1	1	1

이런식으로..끝까지 반복 하기

-> 이후에는 감소하는 dp로 확인하기 (뒤에서부터 시작하기) 

문제 풀이

💻Python(파이썬)

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

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if s[i]>s[j]:
            down[i] = max(down[j]+1,down[i])

sum =0
for i in range(n):
    sum = max(sum,up[i]+down[i])

print(up,down)
print(sum)

💻Java(자바)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] s = new int[N];
        int[] up = new int[N];
        int[] down = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            s[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1;i<N;i++){
            for(int j=0;j<i;j++){
                if(s[j]<s[i]){
                    up[i] = Math.max(up[j]+1,up[i]);
                }
            }
        }
        for(int i=N-1;i>-1;i--){
            for(int j=i;j<N;j++){
                if(s[i]>s[j]){
                    down[i]= Math.max(down[j]+1,down[i]);
                }
            }
        }
        int sum =0;
        for(int i=0;i<N;i++){
            sum = Math.max(sum,up[i]+down[i]);
        }
        System.out.println(sum+1);
    }
}