[백준] 11054 - 가장 긴 바이토닉 부분 수열 (G3)

 

---

문제 소개

---

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

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

가장 긴 증가하는 부분 수열의 응용문제이다.

가장 긴 증가하는 부분 수열의 풀이 과정을 정확하게 이해하고 있다면, 이 문제 역시 어렵지 않게 풀 수 있다.

(골드3 난이도길래 특별한 코너케이스가 숨어있는 줄 알았는데, 다행히 그런 건 없었다.)

 

11053 가장 긴 증가하는 부분 수열

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

 

9465 스티커

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

 

이 두 문제를 정확하게 이해하고 풀 수 있다면, 이 문제를 간단하게 풀 수 있다.

스티커 문제의 포스팅에서도 언급했지만, 직전 상황에 따라 현재 상황이 좌우된다면,

직전의 상황을 상황별로 저장해두면 된다.

---

풀이 아이디어

---

이 문제는 '증가하고 있는 상황' 과 '감소하고 있는 상황' 이 있고,

각각의 상황에 따라서 i번째 수를 포함한 가장 긴 바이토닉 부분수열의 길이가 달라진다.

 

따라서

1. i번째 수를 넣었을 때도 여전히 증가하고 있는 상황

2. i번째 수를 넣었을 때부터 감소 / i번째 수를 넣었을 때도 여전히 감소하고 있는 상황

 

이렇게 두 가지 상황을 나누어서 dp 배열에 저장하면된다.

이때 2번에 해당하는 점화식은 감소하는 상황만 저장하면 안된다.

1, 2, 3, 2, 1

 

이렇게 증가하다가 감소하는 상황을 같이 저장하기 위해서는

기존에 증가하고 있던 수열에 자기 자신을 붙이면서 감소하기 시작하는 경우도 넣어야 한다.

 

1번 상황과 2번상황을 하나의 2차원 배열에 모두 저장하되

1번 상황은 dp[0]에 저장하고

2번 상황은 dp[1]에 저장한다고 해보자

 

그렇다면 각 상황별 점화식은 다음과 같다.

1번 상황 점화식 : dp[0][i] = max(dp[0][0], dp[0][1], ... , dp[0][i-1]) + 1

단, max값이 없을 경우 1 저장 (자기자신만 수열에 존재)

 

0번째부터 i-1번째까지 반복하면서 해당 수를 포함하는 가장 긴 증가하는 수열 길이에 1을 더하여 구한다.

 

2번 상황 점화식 : dp[1][i] = max(dp[0][0], dp[1][0], dp[0][1], dp[1][1], ..., dp[0][i-1], dp[1][i-1]) + 1

단, max 값이 없을 경우 1 저장 (자기자신만 수열에 존재)

 

마찬가지로 0번째부터 i-1번째까지 반복하면서 해당 수를 포함하는 가장 긴 증가하거나 바이토닉인 수열 길이에

1을 더하여 구한다.

---

각 i 마다 0 부터 i-1까지 순회하기에 연산 횟수는 1부터 n까지의 합과 같다.

따라서 시간복잡도는 O(n^2) 이다.

n이 최대 1000 이므로 1초 내에 충분히 풀 수 있다.

---

정답 코드

---

# 11054 가장 긴 바이토닉 부분 수열
n = int(input())
nums = list(map(int, input().split()))
dp = [ [], [] ]
for i in range(n):
    ascendMax, descendMax = 0, 0
    for j in range(i):
        if nums[j] < nums[i]:
            ascendMax = max(ascendMax, dp[0][j])
        if nums[j] > nums[i]:
            descendMax = max(descendMax, dp[1][j], dp[0][j])

    dp[0].append(ascendMax + 1)
    dp[1].append(descendMax + 1)

answer = 0
for i in range(n):
    answer = max(answer, dp[0][i], dp[1][i])

print(answer)

한번 i에 대해 체크할 때 증가하는 부분 수열과, 바이토닉 부분 수열을 동시에 체크하도록 했다.