BOJ(백준) 18353번 병사 배치하기 파이썬

18353번: 병사 배치하기

---

코드

import sys
r = sys.stdin.readline
N = int(r())
soldier = list(map(int,r().split()))

dp = []
dp.append(soldier[0]) # dp = [15]

for i in range(1, N):
    if soldier[i] < dp[-1]:
        dp.append(soldier[i])
    else:
        for j in range(len(dp)):
            if soldier[i] >= dp[j]:
                dp[j] = soldier[i]
                break

print(N - len(dp))

 

해설

문제를 본 후 주어진 값들에서 감소하는 가장 긴 부분 수열 을 구한뒤에 N에서 빼주면 쉽게 문제를 해결할 수 있을꺼라 판단 했습니다. 감소하는 가장 긴 부분 수열을 저장할 빈 리스트 dp 를 생성하고 우선 주어진 수열의 첫 값을 append 했습니다.

주어진 예제의 경우 단순히 dp의 마지막 값인 dp[-1] 에 soldier 리스트가 포문을 순회하며 대소 비교를 한 후 추가하면 되지만 예외적인 경우 이러한 방법이 통하지 않음을 인지 했습니다.

예를들어 soldier 리스트가 [2, 1, 7, 6, 5, 4, 3] 인 경우 단순히 마지막 값과 대소 비교를 하면 dp 가 [2, 1] 후에 더 이상 추가되지 않고 결국 진정한 감소하는 가장 긴 부분 수열인 [7, 6, 5, 4, 3] 을 리턴할 수 없게 됩니다. 이를 해결하기 위해 dp[-1] 보다 soldier[i] 값이 작은 경우는 바로 dp에 추가를 해주었지만 dp[-1] 보다 soldier[i] 의 값이 크거나 같은 경우 dp에 대해 포문을 순회하며 soldier[i] 가 dp[j]d보다 크거나 같은 경우 값을 변경하고 break을 통해 포문을 빠져나오도록 했습니다.

이렇게 하면 [2, 1, 7, 6, 5, 4, 3] 에 대해서 dp가 다음과 같이 변화할 수 있습니다.

[2] -> [2,1] -> [7,1] -> [7,6] -> [7,6,5] -> [7,6,5,4] -> [7,6,5,4,3]

제 풀이는 시간복잡도가 $O(N^2)$ 입니다. 상위권 사람들의 풀이를 보니 이진 탐색을 이용하여 시간복잡도 $O(NlogN)$ 으로 풀이 했음을 알 수 있습니다. 아직 이진 탐색 알고리즘을 구현할줄 몰라서 저렇게 풀지 못했는데 이진 탐색 알고리즘도 곧 공부해야 될 것 같다는 생각이 들었습니다.

 

결과