백준 11504 - 가장 긴 바이토닉 부분 수열

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

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

롸 2시간 넘게 썼는데 아니다 3시간?

이게 수열마다 맞는게 있고 아닌게 있어서 if문으로 조건 엄청 걸다가 포기했다ㅋ

머리가 녹을 것 같다...,,

 

구글링해 본 결과, 전혀 다른 방법으로 접근해서 간단히 풀더라 쩝

나는 이 포스팅을 참고 했는데 이해가 잘 갔다.

 

https://velog.io/@rjqnr928/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-11054%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준 알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 (Python / 파이썬)

 

 

 

이 문제는 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 하는데, 이 바이토닉 수열의 최대 길이를 구하는 문제이다.

백준 11053 문제와 유사하다.

 

 

이 문제에서 바이토닉 수열이란 증가하다가 감소하는 수열이다.

즉, 어떤 수를 기준으로 왼쪽은 증가 수열이고 오른쪽은 감소 수열이다.

어떤 수를 기준으로 왼쪽 증가 수열의 길이와 오른쪽 감소 수열의 길이를 합하였을 때의 최대값을 구하면 된다.

 

 

백준 11053에서는 왼쪽에서의 증가 수열의 최대 길이를 구했었다.

이를 활용하여 증가 수열의 최대 길이를 구하면 된다.

 

 

어떤 수를 기준으로 왼쪽에서 시작해도 증가수열, 오른쪽에서 시작해도 증가수열이기 때문에, 왼쪽 증가 수열은 반복문 0부터 n-1까지 돌리면 되고 / 오른쪽 증가 수열은 거꾸로 반복문을 돌리면 된다.

 

 

따라서 dp_up과 dp_down 두 리스트를 만들어서 각각을 1로 초기화하고, 

각 리스트에 왼쪽부터 시작했을 때 증가하는 부분 수열의 최대 길이와

오른쪽에서부터 시작했을 때 증가하는 부분 수열의 최대 길이를 저장하였다.

 

 

각 리스트의 원소는 각 인덱스를 기준으로 했을 때의 증가 수열의 최대 길이와 감소 수열의 최대 길이가 된다.

여기서, 감소 수열의 최대 길이는 오른쪽에서부터 시작했을 때의 증가 부분 수열의 최대길이이다.

 

 

바이토닉 수열의 최대 길이를 구하기 위해서는, 두 리스트를 합한 후, 최대 값에 1을 빼주면 된다.

1을 빼주는 이유는, 증가 수열과 감소 수열에 둘 다 해당 인덱스의 수가 중복되기 때문이다.

 

 

위 알고리즘 흐름을 적용한 코드는 다음과 같이 구현된다.

 

 

 

풀이코드)

n = int(input())
nums = list(map(int, input().split()))
dp_up = [1] * n
dp_down = [1] * n
total = []
for i in range(n):
    for j in range(i):
        if nums[i]>nums[j]:
            dp_up[i] = max(dp_up[i], dp_up[j]+1)
            
for i in range(n-2, -1, -1):
    for j in range(i+1, n):
        if nums[i]>nums[j]:
            dp_down[i] = max(dp_down[i], dp_down[j]+1)

total = [x+y for x, y in zip(dp_up, dp_down)]
print(max(total)-1)

 

 

*참고*

두 리스트를 합치기 위해 + 를 쓰면 두 리스트가 기차처럼 이어진다.

각 원소끼리 더하고 싶을 경우엔, 여러 방법이 있는데 나는 아래 방법을 사용했다.

a = [1, 2, 3, 4, 5]

b = [5, 6, 7, 8, 9]

c = [x + y for x, y in zip(a,b)]

print(c)

# [6, 8, 10, 12, 14]

 

 

https://tosuccess.tistory.com/113

[파이썬/python] 리스트 요소 간 합

위의 방법 말고도 다른 방법들도 많이 있는데, 위 포스팅에 여러 방법들이 나와있으니 참고하면 좋을 것 같다.