11054

날짜 : 2023. 05. 09

사용 언어 : python

 

문제

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

 

 

코드

import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))   # 수열 입력
up = [0] * n
down = [0] * n
total = [0] * n

for i in range(n):  # 기준
    for j in range(i):
        # 기준값보다 작은 수 + 그 수의 인덱스의 오름차순수열 개수 최신화
        if a[i] > a[j] and up[i] < up[j]:
            up[i] = up[j]
    up[i] += 1
#print(up)
for i in range(n-1, -1, -1):  # 기준값(역순으로 진행)
    for j in range(n-1, i-1, -1):
        if a[i] > a[j] and down[i] < down[j]:
            down[i] = down[j]
    down[i] += 1
#print(down)
for i in range(n):
    total[i] = up[i] + down[i] - 1
print(max(total))

 

 

풀이

- 바이토닉 수열 2개를 합치는 방식으로 풀이한다.

- 오름차순의 바이토닉 수열과 내림차순의 바이토닉 수열을 구한 후 이를 더한 다음, 최대값을 구한 후 중복값을 제하여 아웃풋을 출력한다.

 

 

알게된 점

- dp를 구하는 방식을 떠올리는데 어려움을 느꼈다. 

- 현재 인덱스의 값을 기준으로 그 값보다 작은 수의 케이스의 dp값을 비교하면서 전개하는 아이디어를 생각해 내는데 어려웠다.

- 그래서 이전에 풀었던 문제를 참고했는데 확실히 거의 동일한 문제를 풀 때에도 똑같이 어려움을 느꼈다.

(https://www.acmicpc.net/problem/11053)

 

 

참고 사이트

-