병사 배치하기 백준 18353번 DP

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

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

다이나믹프로그래밍, 메모이제이션으로 나왔지만 처음에 떠오른 생각은 스택을 이용해서 푸는 것이라 그렇게 진행을 해보았습니다.

처음에 리스트를 받아서 순서대로 스택을 넣습니다. 그러다가 반대인 경우

예를 들어서 4를 넣었는데 8이 오는 경우라면 4를 pop하고 8을 넣는 동작을 수행하고 이게 몇번 일어 났는지 계산을 했습니다.

from collections import deque

n = int(input())
solider = list(map(int,input().split()))
solider = deque(solider)
count = 0

now = solider.popleft()
new_stack = deque([])
new_stack.append(now)

while solider:
    check = solider.popleft()
    if now >= check:
        now = check
        new_stack.append(now)
    else:
        new_stack.popleft()
        now = check
        new_stack.append(now)
        count += 1

하지만 실패했다고 나오네요 만족을 하지 못하는 테스트 케이스가 있나 봅니다.

그래서 다시 생각을 해보았습니다. 결국 최대 값이니 순서를 바꾸지 않고 제일 높은 값을 유지해야한다고

일단 해당 문제의 아이디어는 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)로 알려진 전형적인 다이나믹 프로그래밍의 아이디어와 일치합니다. 가장 긴 증가하는 부분 수열 문제란 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제입니다.

예를 들어서 하나의 수열 array = [10,20,10,30,20,50]이 있다고 가정하자 이때 가장 긴 증가하는 부분 수열은 [10,20,30,50]이 될 것이다. D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정의하면 가장 긴 부분 수열을 계산하는 점화식은 다음과 같다.

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))

훨씬 코드가 간단해졌네요, 컴퓨터공학과에서 수업을 들을때 교수님께서 자주 하시는 말씀은 제일 좋은 코드는 쉬운 코드라고 했던 기억이 납니다. (저는 그때 짧은 코드요 했는데 짧기만하고 어렵게 짜는 사람도 많다고 ㅋㅋ 숏코딩 보시면 이해 안되는게 더 많을 겁니다.)

일단 먼저 수열을 뒤집어서 시작을 합니다. 가장 긴 증가하는 부분 수열 알고리즘을 수행하기 위해서인데요

그리고 다이나믹프로그래밍 순열의 순서를 체크하기 위한 테이블을 1로 초기화를 합시다.

일단 첫번째는 비교를 하지 않아도 됩니다. 두번째부터 보기 위해서 1부터 n까지 확인을 하겠습니다. 이어서 이중for문인데 i번까지 반복을 합니다. 그리고 조건에 따라서 테이블을 업데이트 하는데 예시를 들어보겠습니다.

4 2 5 8 4 11 15

array 리스트에는 위 처럼 들어가 있습니다. 일단 이중 for문에서 첫번째 if문에 어떤게 걸리는지 봅시다.

array[0] < array[1] 이고 값으로 보면 4<2 입니다. 조건에 만족하지 않습니다. 첫번째 for문이 종료되고 다음 i=2일때로 봅시다.

i = 2, j = 0

array[0] < array[2] : 4<5 조건을 만족합니다.

dp[2] = max(dp[2], dp[0] + 1) : dp[2] = max(1,1+1) dp[2]는 2로 갱신이 됩니다.

i = 2, j = 1

array[1] < array[2] : 2<5 조건을 만족합니다.

dp[2] = max(dp[2], dp[1] + 1) : dp[2] = max(2,1+1) dp[2]는 2그대로 입니다.

이렇게 dp테이블은 최종적으로 1 2 1 3 2 4 가 들어갑니다. 최대 길이는 4가 되고 n에서 4를 빼면 정답을 구할 수 있습니다.