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

코드

오답 1

• DP 테이블의 값 중 LIS에 해당하는 인덱스를 구하여 문제 풀이
• 증가하는 부분 수열이 하나가 아닌 경우에 오답이 발생
  • 가장 길게 증가하지만 가장 길게 감소하지 않는 경우, 그 값이 항상 크다고 확신할 수 없음
• 주어진 예제는 정답이라 고치는데 애를 먹음

n = int(input())
arr = list(map(int, input().split()))

d = [1 for _ in range(n)]
d2 = [1 for _ in range(n)]

for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            d[i] = max(d[i], d[j] + 1)

max_idx = d.index(max(d))

for i in range(max_idx, n):
    for j in range(i):
        if arr[j] > arr[i]:
            d2[i] = max(d2[i], d2[j] + 1)
            
print(max(d) + max(d2) - 1)

오답 2

• DP 테이블의 각 요소 값들을 인덱스에 맞춰서 더함
• d1 리스트에서 구한 LIS의 인덱스 값에 해당하는 d2의 값이 알맞게 매칭되지 않음
  • 즉, d2의 LDS 값이 d의 LIS 값의 인덱스에서부터 시작됐다는 것을 보장할 수 없음

n = int(input())
arr = list(map(int, input().split()))

d = [1 for _ in range(n)]
d2 = [1 for _ in range(n)]

for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            d[i] = max(d[i], d[j] + 1)
        
        if arr[j] > arr[i]:
            d2[i] = max(d2[i], d2[j] + 1)
            
result = [0 for _ in range(n)]

for i in range(n):
    result[i] = d[i] + d2[i] - 1
print(max(result))

정답

• 주어진 수열을 역정렬한 후, LIS로 re_d(d2)를 구함
  • 역정렬 후 LIS를 구하는 것과 그냥 LDS를 구하는 경우, 최댓값은 같지만 DP 테이블 자체는 달라짐
  • 두 경우가 같다고 생각하여 문제를 풀었다가 이해 자체를 하지 못해서 애를 먹음

n = int(input())
arr = list(map(int, input().split()))

# 주어진 수열 역정렬
re_arr = arr[::-1]

# arr의 DP 테이블
d = [1 for _ in range(n)]

# re_arr의 DP 테이블
re_d = [1 for _ in range(n)]

# 두 수열 모두에 LIS 수행
for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            d[i] = max(d[i], d[j] + 1)
        
        if re_arr[j] < re_arr[i]:
            re_d[i] = max(re_d[i], re_d[j] + 1)
          
# 바이토닉 수열의 길이를 담을 리스트        
result = [0 for _ in range(n)]

# 역정렬한 DP 테이블을 다시 역정렬 수행
# => 그래야 원래의 인덱스와 맞춰서 연산 가능
re_d.reverse()

# 두 리스트의 요소들 끼리 합해주고 1을 빼줌
# -1 수행 이유 : 값이 증가하다가 감소하는 그 값은 연산이 2번 수행됨
for i in range(n):
    result[i] = d[i] + re_d[i] - 1
    
print(max(result))

다름을 증명

n = int(input())
arr = list(map(int, input().split()))

# 역정렬 후 LIS 수행
def solu1(arr):
    re_arr = arr[::-1]

    d = [1 for _ in range(n)]

    for i in range(1, n):
        for j in range(i):
            if re_arr[j] < re_arr[i]:
                d[i] = max(d[i], d[j] + 1)
                
    return d

# LDS 수행
def solu2(arr):
    d = [1 for _ in range(n)]
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] > arr[i]:
                d[i] = max(d[i], d[j] + 1)
    return d

print(solu1(arr) == solu2(arr))
print(max(solu1(arr)) == max(solu2(arr)))

문제 해설

LIS 문제의 응용 버전이다.

오답1과 오답2의 코드를 보면 알 수 있듯이 상당히 헤딩을 많이한 문제. 로직 자체를 연상하는 것은 어렵지 않았으나 생각보다 세밀한 부분에서 반례를 다루는 것이 어려웠다. 특히 주어진 배열에 LDS를 수행하는 것과 역정렬한 배열에 LIS를 적용하는 경우, DP 테이블의 결괏값이 당연히 같을 거라고 생각하여 이 부분의 생각을 부수는데 정말 많은 시간을 소요했다.