728x90
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
LIS
| 문항 | 수열 길이 | 입력값 | 복잡도 |
| 18353 병사배치 | 1 ~ 1,000 | 1~10,000,000 | n² |
| 12738 가장 긴 증가하는 부분 수열2,3 | 1 ~ 1,000,000 | 1~1,000,000 -1,000,000~1,000,000 |
nlogn |
| 14003 가장 긴 증가하는 부분 수열5 | 1 ~ 1,000,000 | -1,000,000,000~1,000,000,000 | nlogn |
분석
N(1~2,000) : 이중 for문으로 풀이
D[i]=array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
모든 0≤j<i에 대하여, D[i]=max(D[i], D[j]+1) if array[j]<array[i]
풀이
n=int(input())
array=list(map(int, input().split()))
#순서를 뒤집어 LIS 문제로 변환
array.reverse()
d=[1]*n
for i in range(1,n):
for j in range(0, i):
if array[j]<array[i]:
# j를 마지막으로 갖는 부분 수열 최대길이 +1와 비교
d[i]=max(d[i], d[j]+1)
# 열외시켜야하는 병사의 최소 수
print(n-max(d))
728x90