[백준] 18353 병사 배치하기

백준 18353번 병사 배치하기

다이나믹 / 가장 긴 증가하는 부분 수열 O(nlogn)

 

 

 

[문제]

 

 

고려해야 할 부분은 항상 전투력이 높은 병사순으로 내림차순 이라는 것

배치 과정에서 특정한 위치에 있는 병사를 열외시켜서 남아있는 병사의 수가 최대가 되도록 하는 것

 

 

 

[과정]

 

'가장 긴 증가하는 부분 수열(LIS)'을 이용해서 풀이

내림차순을 요구하는 문제이기 때문에 점화식의 부등호 방향을 바꾸어주면 됨

 

• dp는 모두 1로 초기화 하고 입력받은 병사들의 전투력을 저장
• 점화식: 모든 0 <= j < i 에 대해, dp[i] = max(dp[i], dp[j]+1) if soldiers[j] > soldiers[i]
• dp의 최댓값 -> 가장 긴 내림차순 부분 수열의 길이
• 전체 병사의 수인 N에서 빼주기

 

 

 

[소스코드]

 

# 병사 배치하기

n = int(input())
data = list(map(int, input().split()))

result = []
dp = [1] * n
for i in range(n):
    for j in range(i):
        if data[j] > data[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(n - max(dp))

 

---

 

 

[통과]