[백준 18353번] 병사 배치하기 - Python

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

18353번: 병사 배치하기

풀이

사용한 알고리즘 : LIS (Longest Increasing Subsequence)

 

원소가 N개인 배열에서 일부 원소를 골라내서 만든 부분수열 중 오름차순을 만족하며,

그 길이가 최대인 수열을 LIS라고 한다.

 

풀이과정

1. 입력값을 저장할 arr, 특정 인덱스에서 내림차순의 LIS 값을 저장할 length 리스트를 정의한다.

2. 0~N-1 인덱스를 돌며 특정 인덱스에서 해당 값이 가질 수 있는 LIS를 구한다.

    i 번째 반복일 때.  a) arr[i] =1

                                 b) j가 0~i-1까지 반복하며 arr[j]>arr[i]면 max(arr[i],arr[j]+1)을 통해

                                     i 위치에서 가질 수 있는 LIS 값을 구하고 length[i]에 저장한다.

import sys

input=sys.stdin.readline

N=int(input())
arr=list(map(int,input().split()))
length=[0]*N

for i in range(N):
    length[i]=1
    for j in range(i):
        if arr[j]>arr[i]:
            length[i]=max(length[i],length[j]+1)

print(N-max(length))