반응형
https://www.acmicpc.net/problem/18353
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 |