[python] 백준 18353 - 병사 배치하기

출처 : 백준, https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

 

# 병사의 전투력 리스트가 주어진다

# 가장 긴 감소하는 부분 수열을 만들 수 있는 열외 병사의 수

 

 

먼저, 생각해야 할 부분

 

1. 가장 긴 감소하는 부분 수열을 만들 수 있는 병사의 수는 전체 병사의 수에서 가장 긴 감소하는 부분수열의 길이를 빼면 된다.

 

 

---

 

풀이

 

def solution(n, num_list):
    # 이전에 있는 것들 중 나보다 크면서 최대 길이가 가장 큰 것

    dp = [1 for _ in range(n)]

    for i in range(1, n):
        # 나보다 작은 idx 중에
        # 가장 긴 길이를 찾아서 + 1
        for j in range(i):
            if num_list[j] > num_list[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return n - max(dp)

n = int(input())
num_list = list(map(int, input().split()))

print(solution(n, num_list))

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들