[이코테] 다이나믹 프로그래밍 - 병사 배치하기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

18353번: 병사 배치하기

사고과정

• DP의 전형적인 '뒤의 입장에서'를 생각하고 풀어보려 했지만 구현은 했지만 다른 테스트 케이스를 통과하지 못했다..
• 도저히 모르겠어서 풀이를 보았고 가장 긴 증가하는 부분 수열 길이를 구하는 LIS 알고리즘에 대해 배우게 되었다. 그리고 블로깅도 해놓았음.. 개념은 여기를 참고하자.
• 주의할 점은 해당 문제에서는 병사 전투력을 내림차순으로 정렬하라고 했다. 그런데 위에서 언급한 LIS 알고리즘은 오름차순으로 증가하는 부분 수열의 가장 긴 길이를 찾는 것이다. 따라서 문제에서 주어진 병사 전투력을 reverse(거꾸로 뒤집은) 한 뒤 LIS를 적용하면 된다. 또는 부등호를 반대로 바꾸어 주어도 정답 처리가 된다. 그리고 전체 병사 명수에서 가장 긴 증가하는 부분 수열의 길이를 빼주면 정답이 된다.

풀이(스스로 못 푼 풀이)

1. 애초에 주어진 데이터를 reverse 시키고 LIS 알고리즘 적용

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

# DP 테이블 값을 1로 초기화
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))

2. 주어진 데이터를 그대로 사용하되 LIS 알고리즘 내부에서 부등호 방향만 바꾸어주기

n = int(input())
array = list(map(int, input().split()))
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)

res = n - max(dp)
print(res)