백준 문제풀이 - 18353 번

링크 -> https://www.acmicpc.net/problem/18353

1. 요약 및 풀이방법

병사가 무작위로 나열되어 있습니다.
특정 위치의 병사를 열외시켜 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하려고 할 때,
남아있는 병사의 수가 최대가 되도록 하는 문제입니다.

이 문제는 동적 프로그래밍 알고리즘의 기본적인 문제인 가장 긴 증가하는 부분수열을 구하는 문제와 유사합니다.
반대로 가장 긴 감소하는 부분 수열을 구하면 됩니다.

https://velog.io/@hyungraelee/Python-백준-문제풀이-1965번

이 문제에서 max(dp)는 가장 긴 병사들의 집합이므로,
전체 병사에서 집합 할 병사의 수를 제외하면 열외하는 병사의 수를 구할 수 있습니다.

2. Code

def main():
    N = int(input())
    soldiers = list(map(int, input().split()))
    dp = [1] * N

    for i in range(N):
        for j in range(i):
            if soldiers[j] > soldiers[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    print(N - max(dp))

if __name__ == "__main__":
    main()

3. 학습 내용

기본적인 동적 프로그래밍 알고리즘으로도 이렇게 다양한 실생활 문제가 나올 수 있습니다.
따라서 카테고리를 모를 때 이 문제를 보고, 동적 프로그래밍 알고리즘을 생각하는 것이 더 중요합니다.

4. 결과