💡Problem Solving/BOJ
[BOJ 18353] 병사 배치하기 (Python)
gom20
2022. 11. 22. 12:04
문제
https://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
LIS 알고리즘 사용.
DP방식으로 이중 For문 사용하여 구현
[Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)
LIS 알고리즘이란? LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 풀이 1. DP로 풀기 시간 복잡도 O(N^2) 이
gom20.tistory.com
소스코드
n = int(input())
arr = list(map(int, input().split()))
arr.reverse()
# print(arr)
dp = [1]*n
for i in range(1, n):
for j in range(0, i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], 1 + dp[j])
print(n-max(dp))