백준18353번 병사 배치하기 2021.06.16 병사배치하기 Solution LIS (Longest Increasing Sequence) 를 내림차순으로 변형하여 풀이하였습니다. 0 ~ N-1 을 돌며 DP[N]을 구합니다. (n) DP[N] = DP[N-i] + 1 (i = 0 ~ n-1) N-i번보다 N번이 작으면 N-i번 오른쪽에 N번이 위치할 수 있고, 이렇게 했을 때 N-i번의 최대 길이에 +1 한 것이 N번의 최대길이 후보가 됩니다. 0 ~ n-1 을 돌며 왼쪽 부분수열 중 n번이 오른쪽에 놓일 수 있는 후보를 고릅니다. +1 한 값과 비교해 DP[n]을 업데이트합니다. DP[N] 중 최댓값을 N에서 뺀 값이 정답입니다. Source # 2021.06.16 병사배치하기 # Solution :..