알고리즘/BOJ

[BOJ] 18353 - 병사 배치하기

서노리 2022. 2. 14. 23:12
반응형

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

 

18353번: 병사 배치하기

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().rstrip().split()))

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

print(n - max(dp))

이 문제의 기본 아이디어는 '가장 긴 증가하는 부분 수열(LIS)'로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다. '가장 긴 증가하는 부분 수열' 문제란, 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다. 이 문제에서는 이를 가장 긴 감소하는 부분 수열 문제로 수정하여 해결할 수 있다.

 

처음 DP 테이블을 모두 1로 초기화한후, 두 번째 병사부터 앞에 있는 병사들과 비교하면서 전투력이 더 작다면 해당 병사까지의 최대 수열 길이 + 1을 저장하면 된다. 이를 코드로 나타낸 부분은 다음과 같다.

for i in range(1, n):
    for j in range(0, i):
        if data[i] < data[j]:
            dp[i] = max(dp[i], dp[j] + 1)

 

이 문제에서는 N이 2,000 밖에 되지 않아 O(N^2)의 시간 복잡도로 문제를 풀 수 있었지만 만약 O(N log N)의 시간 복잡도가 필요한 경우 이진 탐색을 이용하여 이를 해결할 수 있다. 이에 관한 포스팅 -> [BOJ] 12015 - 가장 긴 증가하는 부분 수열 2

 

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1149 - RGB거리  (0) 2022.02.18
[BOJ] 12015 - 가장 긴 증가하는 부분 수열 2  (0) 2022.02.15
[BOJ] 14501 - 퇴사  (0) 2022.02.14
[BOJ] 2110 - 공유기 설치  (0) 2022.02.06
[BOJ] 1654 - 랜선 자르기  (0) 2022.02.02