병사 배치하기

1. 문제 설명

출처 : 이코테2021

---

2. 문제 조건

---

3. 문제 해결 아이디어

• 기본 아이디어는 가장 긴 증가하는 부분 수열(LIS) 
• 예를들어 array = {4,2,5,8,4,11,15}
  • 가장 긴 증가하는 부분 수열은 {4,5,8,11,15}

 

[Step 0]

• 우선 값이 1이 될 수 있도록 모두 1로 초기화한다.

 

[Step 1]

• 2부터 시작한다.
• 앞에 4라는 인덱스가 1개존재한다.
• 점화식에 의해 4는 2보다 크므로 그대로 유지한다.

 

[Step 2]

• i = 2일 경우를 살펴보자
• 인덱스2의 값인 5를 확인한다.
• 4와 비교했을때 5가 크므로 4의 값에 1을 더해 2가된다.
• 인덱스1의 값인 2를 비교했을때 1<2 이므로 갱신되지 않고 종료된다.

 

• 이와같이 완성이 된다.
• 마지막은 7번째 인덱스 (15)를 마지막 길이로 가지는 형태로 계산한다.

---

4. 답안

n = int(input())
array = list(map(int,input().split()))
#순서를 뒤집어 최장 증가 부분 수열 문제로 변환
array.reverse()

#DP 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS)알고리즘 수행
for i in range(1, n):
    for j in range(0,i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))