백준 병사 배치하기 코드 및 해설 (파이썬)

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net '가장 긴 증가하는 부분 수열(LIS)'을 이용해 풀이했습니다. 이 문제는 오름차순이 아니라 내림차순을 요구하므로, 점화식의 부등호 방향만 바꾸어줬습니다. dp는 모두 1로 초기화하고, soldiers는 입력으로 받은 병사들의 전투력을 저장합니다. 점화식: 모든 0 soldiers[i] 이후 dp의 최댓값을 구하면 가장 긴 내림차순 부분 수열의 길이가 되고, 이를 전체 병사의 수인 N에..

2021.07.29