백준 파이썬 11054 가장 긴 바이토닉 부분 수열

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

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

 

 

처음에는 늘어나는 부분 수열과 줄어드는 부분 수열을 한 dp배열에 전부 넣으려고 했지만

얼토당토 없는 결과 값이 나왔고 이 방법이 아닌 다른 방법을 생각해봤다.

 

차근차근 풀이를 했는데

 

일단 가장 긴 늘어나는 부분 수열을 구해보았는데.

(예시)

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

# n = 10
# s = [1 5 2 1 4 3 4 5 2 1]

n = int(input())

s = list(map(int,input().split()))

dp=[1]*n

for i in range(n):
    for j in range(i):
        if s[i] > s[j]:
            dp[i] = max(dp[i],dp[j]+1)
            
 print(dp) # [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]

 

늘어나는 부분 수열 =  [1, 2, 2, 1, 3, 3, 4, 5, 2, 1] 

 

이 부분에서 역순으로 늘어나는 부분 수열을 따로 만들었고 그 수를 더해주었더니 생각했던 대로 값이 반환되었음.

 

# n = 10
# s = [1 5 2 1 4 3 4 5 2 1]

n = int(input())

s = list(map(int,input().split()))
s_2 = s[::-1]

dp=[1]*n
dp_2=[1]*n

for i in range(n):
    for j in range(i):
        if s[i] > s[j]:
            dp[i] = max(dp[i],dp[j]+1)
        if s_2[i] > s_2[j]:
            dp_2[i] = max(dp_2[i],dp_2[j]+1)


dp_2 = dp_2[::-1]

answer = [0 for i in range(n)]
for i in range(n):
    answer[i] = dp[i] + dp_2[i] - 1

print(max(answer))

#dp([1, 2, 2, 1, 3, 3, 4, 5, 2, 1])
#dp_2([1, 5, 2, 1, 4, 3, 3, 3, 2, 1])

 

그렇게 어렵지 않은 문제였고 

https://seohyun0120.tistory.com/entry/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC

예전에 이 분이 올려주신 글을 생각하며 풀이를 생각해냈습니다잉

가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬