문제
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))
'💡Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ 2887] 행성 터널 (Python) (0) | 2022.11.23 |
|---|---|
| [BOJ 11404] 플로이드 (Python) (0) | 2022.11.22 |
| [BOJ 1715] 카드 정렬하기 (Python) (0) | 2022.11.19 |
| [BOJ 18310] 안테나 (Python) (0) | 2022.11.19 |
| [BOJ 10825] 국영수 (Python) (0) | 2022.11.19 |