LIS ( 가장 긴 증가하는 부분 수열)

문제

N명의 병사가 무작위로 나열되어 있을 때, 전투력을 기준으로 내림차순이 되도록 배치를 하고자 한다. 이를 위해서 특정한 위치에 병사를 열외시키는 방법을 사용한다고 했을 때 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하기

LIS (Longest Increasing Subsequence)

LIS로 알려진 전형적인 다이나믹 프로그래밍 문제이다. '가장 긴 증가하는 부분 수열'문제란, 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다.

예를 들어, array = {10, 20, 10, 30, 20, 50} 으로 가정했을 때, 가장 긴 증가하는 부분수열은 {10, 20, 30, 50}이 될 것이다.

적용

병사 배치에서 가장 긴 증가하는 부분 집합을 찾고 병사의 수인 N에서 빼주기

모든 0 <= j < i에 대하여, D[i] = max(D[i], d[j] + 1) if array[i] < array[j]

1. 먼저, dp테이블을 1로 전부 초기화 시키고 병사 배열을 reverse() 시킨다.
2. i를 1부터 n -1까지 반복하면서 현재를 마지막 원소로 생각하면서 이전의 값들과 비교해본다.
3. 만약 현재 값이 비교하는 j보다 크다면 이어질 수 있기 때문에 현재 값과 array[j]의 값에 1을 더한 값 중 큰 값으로 세팅한다.
4. 결과적으로, dp테이블에서 가장 큰 값이 가장 길게 만들 수 있는 부분 수열의 길이가 된다.
5. 병사의 수에서 이를 빼게 되면, 빼야 하는 병사의 최소 수를 도출해 낼 수 있다.

나의 풀이

# LIS 
n = int(input())
array = list(map(int, input().split()))
array.reverse()

dp = [1] * n

answer = 1
for i in range(1, n):
    for j in range(i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)
            answer = max(answer, dp[i])

print(n - answer)

답안

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '가장 긴 증가하는 부분 수열' 문제로 변환
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# 열외시켜야 하는 병사의 최소 수를 출력
print(n - max(dp))

오류 해결

처음에 answer = 0으로 설정하여서 코드를 돌렸더니 90%에서 틀렸다고 나왔다. 이러한 상황은 만약에, 모든 수열이 내림차순으로 정렬이 되어있다면 answer은 1이 되기 때문에 처음에 1로 초기화를 해줘도 되고 아니면 답안처럼 최대값을 출력해주는 것도 좋을 것 같다.

https://www.acmicpc.net/problem/18353

처음 보는 유형의 문제여서 DP 유형의 문제인 것을 확인하고 들어갔지만 해결법을 찾지 못하였고 LIS 알고리즘에 대해서 새롭게 배우게 되었다.