[백준] 병사 배치하기

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

분류:: LIS ,dp

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

  1. LIS 가장 긴 증가하는 부분수열

#병사 배치하기
#https://www.acmicpc.net/problem/18353
import sys
sys.stdin = open("input.txt","r")

n=int(input())
arr=list(map(int,input().split()))
arr.reverse()
dp=[1]*n #최소 한개의 길이는 가짐

for i in range(n): #arr[i]가 마지막항일때
    for j in range(i): #i보다 작은 것들 중
        if arr[j]<arr[i]: #i가 마지막 항이 가능한 경우 
            dp[i]=max(dp[i],dp[j]+1) #현재길이와 이전길이+1의 큰 값중 선택

print(n-max(dp))

 

3. 오답원인

 

4. 알게된 점

문제에서 정렬을 보면  !

- 이진탐색, 가장 긴 증가하는 부분수열, 감소수열 떠올리자