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

링크

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

난이도(solved.ac 참고)

실버2

풀이

앞서 포스팅한 LIS 문제를 이해했으면 어렵지 않게 풀 수 있는 문제다. 다만 차이가 있다면, a[i]의 값이 더 작은 경우에 dp의 값을 배정해 줬다는 것이다. 그 이유는 여기에서는 증가하는 부분수열이아니라 감소하는 부분수열이기 때문이다.

 

여기에서 우리가 구해야하는 것은, 최대 부분수열의 길이가 아니라 전체에서 최대 부분수열의 길이만큼 빼준 값이기 때문에 대상이 되는 리스트 a의 길이에서 감소하는 최대 부분수열의 길이만큼을 빼준 값이 정답이 된다.