[PS][BOJ/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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

문제 분석 과정

바이토닉 수열이란? : (증가하는 수열 + 감소하는 수열) or (증가 하는 수열) or (감소하는 수열)

바이토닉 수열 10, 20, 30, 40
바이토닉 수열 50, 40, 25, 10
바이토닉 수열 아님 1, 2, 3, 2, 1, 2, 3, 2, 1
바이토닉 수열 아님 10, 20, 30, 40, 20, 30

가장 긴 바이토닉 수열의 점화식은 어떻게 될까..?
증가하는 수열의 dp 값과 감소하는 수열의 dp의 합의 MAX 값이 정답이 될것이다 .
dp = increaseDP+decreaseDp
result = max(dp)

가장 긴 증가하는 수열을 생성하기위해 increaseDP 초기화
increDp = [1]*(n+1)

가장 긴 감소하는 수열을 생성하기위해 increaseDP 초기화
decreDp = [1]*(n+1)

1로 초기화하는 이유는? i번째 인덱스는 무조건 선택되기 때문에 길이는 1 디

만나는 지점에서 두번 카운팅하기때문에 -1 씩 빼줘야한다.

increDP[i] 끝나는 증가하는 수열의 길이
decreDp[i] 시작하는 감소하는 수열의 길이

테스트 케이스 실행결과

10
1 5 2 1 4 3 4 5 2 1 |arr
1   2     3 4 5     |increDP
                2 1 |decreDp 

소스코드

    n = int(input())
    arr = [11] + list(map(int,input().split()))

    # 바이토닉 수열 10, 20, 30, 40
    # 바이토닉 수열 50, 40, 25, 10
    # 바이토닉 수열 아님 1, 2, 3, 2, 1, 2, 3, 2, 1
    # 바이토닉 수열 아님 10, 20, 30, 40, 20, 30
    # 바이토닉 수열이란? :  (증가하는 수열 + 감소하는 수열) or (증가 하는 수열) or (감소하는 수열)

    # 가장 긴 바이토닉 수열의 점화식은 어떻게 될까..? 
    # 증가하는 수열의 dp 값과 감소하는 수열의 dp의 합의 MAX 값이 정답이 될것이다 .
    # dp = increaseDP+decreaseDp
    # result = max(dp)

    # 가장 긴 증가하는 수열을 생성하기위해 increaseDP 초기화 
    increDp = [1]*(n+1)

    # 가장 긴 감소하는 수열을 생성하기위해 increaseDP 초기화 
    decreDp = [1]*(n+1)

    # 1로 초기화하는 이유는? i번째 인덱스는 무조건 선택되기 때문에 길이는 1 
    # 만나는 지점에서 두번 카운팅하기때문에 -1 씩 빼줘야한다.

    #increDP[i] 끝나는 증가하는 수열의 길이
    #decreDp[i] 시작하는 감소하는 수열의 길이

    # 테스트 케이스 
    # 10
    # 1 5 2 1 4 3 4 5 2 1
    # 1   2     3 4 5    
    #                 2 1

    for i in range(1,n+1):
        for j in range(1,i+1):
            if arr[i]>arr[j]:
                increDp[i] = max(increDp[i], increDp[j]+1)

    for i in range(n,0,-1):
        for j in range(n,i,-1):
            if arr[i]>arr[j]:
                decreDp[i] = max(decreDp[i], decreDp[j]+1)

    dp = [increDp[i]+decreDp[i]-1 for i in range(1,n+1)]
    result = max(dp)

    print(result)

분류

다이나믹 프로그래밍(dp)

문제 원본
소스코드 원본