[백준/18353] 병사 배치하기

출처: https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

---

 전형적인 LIS(Longest Increasing sequence) 문제이다. 여기서는 내림차순으로 정렬한다고 했으므로 엄밀히 말하면 LDS(Longest Decreasing sequence) 문제이겠으나, 접근방법은 같다.

 

 처음에는 다음과 같이 간단하게 접근해보려 했다.

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

cnt = 0
prev = array[-1]

for i in range(n - 1, 0, -1):
    if array[i - 1] < prev:
        cnt += 1
        continue
    prev = array[i - 1]

print(cnt)

 리스트를 순회하며 앞 인덱스의 원소가 기준보다 작을 경우 카운팅하는 방식이다. 그러나 위와 같이 접근할 경우 예외가 발생한다. 예를 들어 입력으로 주어진 배열이 [11, 4, 3, 2, 5]라고 해보자. 처음에는 2와 5를 비교하여 2가 5보다 작으므로 카운팅을 할 것이다. 이때 2가 삭제된 셈치므로 기준점은 여전히 5이다. 다음엔 3과 5를 비교하여 3 또한 5보다 작으므로 카운팅된다. 마찬가지로 4까지 카운팅되어 결과로 3이 반환된다. 그러나 사실 이 경우는 5만 제거하면 가장 긴 감소하는 수열을 만들수 있다. 따라서 정답은 1이다.

---

 따라서 이 문제는 다음과 같이 DP 알고리즘으로 접근하는 것이 타당하다.

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

table = [1] * n
for i in range(1, n):
    for j in range(0, i):
        if array[j] > array[i]:
            table[i] = max(table[j] + 1, table[i])

print(n - max(table))

 DP table을 1로 초기화하고, 앞에서부터 리스트를 순회하며 이전의 인덱스들에 대해 모두 확인한다. 이전 인덱스의 전투력이 현재 인덱스의 전투력보다 큰 경우에만 고려하여, 테이블을 초기화시킨다. 즉 테이블에 들어가는 정보는 해당 인덱스까지의 최대 배열 길이이다. 

 

 문제에서 요구하는 것은 '열외시켜야 하는 최소 병사의 수'이므로 배열의 전체 길이에서 정렬된 배열의 최대 길이를 빼주면 원하는 정답을 얻을 수 있게 된다. 

 

---

추가

 추가적으로 아예 리스트를 반대로 뒤집거나, 혹은 뒤쪽 인덱스부터 고려하여 진짜 LIS 문제로 바꾸는 방법도 있다.

 

1. 리스트를 반대로 뒤집는 경우

n = int(input())
array = list(map(int, input().split()))
array.reverse()

table = [1] * n
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            table[i] = max(table[j] + 1, table[i])

print(n - max(table))

2. 뒤쪽 인덱스부터 고려하는 경우

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

table = [1] * n
for i in range(n - 2, -1, -1):
    for j in range(i, n):
        if array[j] < array[i]:
            table[i] = max(table[j] + 1, table[i])

print(n - max(table))