Computer Science/Algorithm
[Baekjoon] DP - 18353 병사 배치하기
ddu0422
2023. 9. 26. 19:32
문제
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
import sys
n = int(sys.stdin.readline().rstrip())
numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
def soluion(a):
d = [1] * len(a)
for i in range(1, len(a)):
for j in range(1, i):
if a[i] < a[j] and d[i] < d[j] + 1:
d[i] = d[j] + 1
return len(a) - 1 - max(d)
print(soluion(numbers))
채점 결과
