[Algorithm] 11054. 가장 긴 바이토닉 부분 수열

11054 : 가장 긴 바이토닉 부분 수열 (LIS)

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

• 문제 티어 : G4
• 풀이 여부 : Failed → Solved
• 소요 시간 : 21:24

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))

increase_dp = [1 for _ in range(N)]
decrease_dp = [1 for _ in range(N)]

# 최대 증가 부분 수열 길이 찾기
for i in range(N):
  for j in range(i):
    if arr[i] > arr[j] and increase_dp[i] < increase_dp[j]+1:
      increase_dp[i] = increase_dp[j] + 1

# 최대 감소 부분 수열 길이 찾기
for i in range(N-1, -1, -1):
  for j in range(N-1, i, -1):
    if arr[i] > arr[j] and decrease_dp[i] < decrease_dp[j] + 1:
      decrease_dp[i] = decrease_dp[j] + 1

# 각 지점 기준 최대로 증가하는 부분 수열, 최대로 감소하는 부분 수열의 길이 중 최댓값 산출
ans = max(increase_dp[i] + decrease_dp[i] - 1 for i in range(N))
print(ans)

접근 방식

풀이 방법을 확인하고, 바이토닉 증가 부분 수열에서는 2번의 반복문을 돌려야 함을 알았다.

1. 최대 증가 부분 수열의 길이를 찾기 위한 반복
2. 최대 감소 부분 수열의 길이를 찾기 위한 반복

위와 같이 2번의 (worst : N^2) 반복을 통해 증가/감소 부분수열을 구해준다.

내가 작성했던 코드와 다른 점이 있다면, increase_dp와 decrease_dp를 산출한 뒤, 각 지점 모두 후보가 될 수 있으므로 ans = max(increase_dp[i] + decrease_dp[i] - 1 for i in range(N)) 로 모든 인덱스를 살펴본다.

접근 시행착오(+ 코드)

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))

increase_dp = [1 for _ in range(N)]
decrease_dp = [1 for _ in range(N)]

for i in range(N):
  for j in range(i):
    if arr[i] > arr[j] and increase_dp[i] < increase_dp[j]+1:
      increase_dp[i] = increase_dp[j] + 1

turn = increase_dp.index(max(increase_dp))

for i in range(turn, N):
  for j in range(i):
    if arr[i] < arr[j] and decrease_dp[i] < decrease_dp[j] + 1:
      decrease_dp[i] = decrease_dp[j] + 1

ans = max(increase_dp) + max(decrease_dp) - 1
print(ans)

처음 접근한 방식은 LIS를 사용해서 최대로 증가하는 위치를 찾고,
그 위치를 기반으로 증가 수열 → 감소 수열로의 전환 후 최대로 감소하는 값을 찾아서 ans를 갱신해줬다.
테스트케이스와 추가로 만든 테스트케이스에 잘 동작했지만 틀렸다.

틀린 이유는 각 위치에서의 최대 증가 부분 수열과 최대 감소 부분수열을 독립적으로 고려해주지 않았기 때문이라고 한다.

바이토닉 부분 수열은 어떤 지점에서도 증가부분과 감소부분이 만나는 지점이 될 수 있고, 각 지점마다 최대 증가 부분 수열과 최대 감소 부분 수열의 합을 고려해줘야 한다는 점을 알았다.

배운점 또는 느낀점

LIS는 생소해서 그런지 잘 활용이 안되어서 아무래도 코드를 외워야 할 것 같다!!!
관련 문제 많이 풀이하면서 필요할 때 바로 떠올려서 사용할 수 있도록 해야겠다 💪