[백준] 18353번 병사 배치하기(feat. 다이나믹 프로그래밍, LIS알고리즘)

 

첫번째 단계

문제를 살펴보자.
N명의 병사가 무작위로 나열되어 있고, 각 병사는 특정한 값의 전투력을 보유하고 있다.
우리는 병사를 배치할 건데, 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치할 것이다.
다시말해, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

그리고, 배치 과정에는 특정 위치에 있는 병사를 열외시키는 방법으로 이용해야 한다.
그러면서도 남아있는 병사의 수가 최대가 되도록 해야한다.

1. 큰 문제를 작은 문제로 나눌 수 있다.(최적 부분 구조)

이 문제는, 이 문제는 병사들을 전투력을 기준으로 내림차순으로 정렬시키면서,
가장 많은 병사가 남아있도록 해야한다.
특정 병사를 열외할지 말지로 문제를 쪼갤 수 있다.
따라서, 이 문제는 최적 부분 구조를 만족한다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.(중복되는 부분 문제)

 

이 문제는, 작은 문제로 나눈 "특정 병사의 열외 여부"가 주어진 배열의 가장 긴 감소하는 부분 수열을 구하는데 이용된다. 
따라서, 이 문제는 중복되는 부분 문제를 만족한다.

따라서, 이 문제는 다이나믹 프로그래밍으로 풀이를 진행할 수 있다.

---

두번째 단계

DP Table을 정의 해보자.
즉, 상태를 정의해보자는 의미이다.

i를 병사 번호라고 하면,
dp[i]는 현재 병사번호가 i일때  i까지 감소하는 부분 수열의 길이 일 것이다.

인덱스를 고려하면,
dp[0]은 병사 번호 1까지의 감소하는 부분수열의 길이를 의미할 것이다.
dp[1]는 병사 번호 2까지의 감소하는 부분수열의 길이를 의미할 것이다.

그리고 이런식으로 dp[n]을 구하면 마지막 병사번호 n까지의 가장 긴 감소하는 부분수열을 구할 수 있을 것이다.

 

 

---

세번째 단계

점화식을 정의하기에 앞서 알아두어야 할 개념이 있다.

 

LIS(Longest Increasing Subsequence) 알고리즘 동작과정을 이해해 보자.

우선, 가장 긴 증가하는 부분수열이란 무엇일까?

위 수열에서 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 수열이 바로 가장 긴 증가하는 부분 수열을 의미한다.
이때 수열의 원소들을 아무것도 건드리지 않고 부분 길이가 가장 긴 것을 찾는게 아니라 수열에서 임의의 원소들을 삭제했을 때 나올 수 있는 가장 긴 길이의 증가하는 부분 수열을 의미한다.  위 수열에서는 3번째, 5번째 값인 10, 20을 빼주면 10-20-30-50으로 가장 긴 길이의 증가하는 부분 수열이다.
이러한 방식으로 그 가장 긴 수열의 길이를 찾는 알고리즘이 LIS 알고리즘이다.

LIS 알고리즘 동작 과정을 좀더 자세히 알아보자.

LIS 알고리즘이 어떻게 가장 긴 증가하는 부분 수열의 길이를 찾는지 살펴보자. 여기서 다이나믹 프로그래밍의 DP 테이블을 활용하는데, 
DP 테이블의 원소값은 주어진 수열의 특정 값을 마지막 원소로 가지는 부분 수열의 최대 길이를 의미한다.
그래서 초기 DP 테이블 값은 모두 자기 자신의 원소를 의미하는 것으로 1로 초기화 해준다.

이제 수열에서 2번째 값(20) 부터 하나씩 확인해서 2번째 값이 직전의 값보다 크다면 DP 테이블에서 2번째 값을 업데이트 시켜준다.
이 때, 점화식을 활용하는데, 업데이트전 DP 테이블의 2번째 값과 DP 테이블의 1번째 값에 1을 더한 값 중 최댓값을 업데이트 시켜준다.
점화식으로 나타내면 다음과 같다.

따라서 2번째 값에 대해 DP 테이블을 갱신해주면 다음과 같아진다.

다음은 3번째 값인 10 차례이다. 3번째 값인 10은 직전 값인 (두번째 값) 20보다 작고 20의 직전 값(첫번째 값)인 10과 같기 때문에 해당 점화식으로 처리하지 않고 무시하고 DP 테이블을 갱신하지 않는다. 눈치가 빠른 사람이라면 3번째 값을 처리할 때 2번째 값을 처리할 때 보다 점화식 조건 절차를 한 번 더 했다는 것을 눈치챌 것이다. 결국 수열의 인덱스가 늘어날 수록 확인하는 절차는 선형적으로 증가한다.
예를 들어 수열의 10번째 값을 확인한다고 하면 1~9번째 값까지 총 9번을 대소비교하면서 조건에 만족하면 점화식 처리를 해야 한다.

따라서 위와 같은 과정을 반복해서 수열의 마지막 원소 인덱스 위치까지 확인 절차를 걸치면 아래와 같이 DP 테이블이 최종 갱신된다.

최종 DP 테이블에서 가장 원소가 큰 값 즉, 빨간색으로 된 4라는 값이 바로 가장 긴 증가하는 부분 수열 길이를 의미하게 된다.

n = int(input())  # 수열의 길이
array = list(map(int, input().split()))  # 주어진 수열

# DP 테이블 1로 초기화
dp = [1] * n

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)

# 가장 긴 증가하는 부분 수열의 길이값
result = max(dp)
print(result)

LIS 알고리즘을 Python으로 구현한 것이다. 

 

LIS알고리즘을 이해했으면,
이제 점화식을 정의해보자.

이 문제에서 LIS를 좀더 직관적으로 사용하기 위해 입력을 뒤집어서 입력받아서 내림차순 문제를 오름 차순으로 바꿔 줄 수 있다.

이 문제의 상태를 병사 열외 유무에 따른 가장 긴 감소하는 부분수열의 길이로 정했다.
그렇다면, 코드의 로직은 크게 2가지로 나눌 수 있을 것이다.

•  병사 번호 i를 열외하면,
  
  • dp[i] = d[i]  # 병사 번호 i를 열외했으므로 그 이전 길이와 같음
• 병사 번호 i를 열외하지 않으면
  
  • dp[i] = dp[j] + 1  # 병사 번호i를 열외하지 않으므로  dp[j] 의 길이에 + 1 한 길이와 같음

이 두 값을 max로 비교해서 dp[i]에 넣어주면 될 것이다.
왜냐하면 dp테이블에는 내림차순으로 가장 긴 증가하는 부분 수열의 길이가 저장될 것 이기 때문이다.

 

 

코드 작성

n = int(input())
# print(n)
soldier = list(map(int, input().split()))
soldier.reverse() # LIS 알고리즘을 직관적으로 이용하기 위해 내림차순 입력을 오름차순 입력으로 바꿈
# print(soldier)

dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if soldier[j] < soldier[i]: 
            dp[i] = max(dp[i], dp[j] + 1)
# 이 문제는 LIS(Longest Increasing Subsequence) 알고리즘을 적용하는 문제다.
print(n-max(dp)) # 그러면 dp테이블에는 가장 긴 감소하는 부분 수열 길이가 저장되므로 문제 조건에 따라 (전체길이-가장긴부분수열길이)를 해준 값이 결과다.