https://www.acmicpc.net/problem/18353
풀이
사용한 알고리즘 : LIS (Longest Increasing Subsequence)
원소가 N개인 배열에서 일부 원소를 골라내서 만든 부분수열 중 오름차순을 만족하며,
그 길이가 최대인 수열을 LIS라고 한다.
풀이과정
1. 입력값을 저장할 arr, 특정 인덱스에서 내림차순의 LIS 값을 저장할 length 리스트를 정의한다.
2. 0~N-1 인덱스를 돌며 특정 인덱스에서 해당 값이 가질 수 있는 LIS를 구한다.
i 번째 반복일 때. a) arr[i] =1
b) j가 0~i-1까지 반복하며 arr[j]>arr[i]면 max(arr[i],arr[j]+1)을 통해
i 위치에서 가질 수 있는 LIS 값을 구하고 length[i]에 저장한다.
import sys
input=sys.stdin.readline
N=int(input())
arr=list(map(int,input().split()))
length=[0]*N
for i in range(N):
length[i]=1
for j in range(i):
if arr[j]>arr[i]:
length[i]=max(length[i],length[j]+1)
print(N-max(length))
'알고리즘||코딩테스트 > 백준' 카테고리의 다른 글
[백준 1365번] 꼬인 전깃줄 - Python (0) | 2023.07.08 |
---|---|
[백준 2550번] 전구 - Python (0) | 2023.07.07 |
[백준 2470번] 두 용액 - Python (0) | 2023.07.05 |
[백준 19598번] 최소 회의실 개수 - Python (0) | 2023.07.04 |
[백준 17266번] 어두운 굴다리 - Python (0) | 2023.07.03 |