[이코테 Ch16-34] 병사 배치하기

👩🏻‍💻문제설명

[이코테 Ch16-34] 병사 배치하기

✍️Idea Sketch

문제요약

병사들을 전투력 기준으로 내림차순 배치하고 싶다. 단, 전투력 중복은 허용되지 않으며, 병사를 열외시켜 내림차순 배치한다. 이 때 예외되지 않고 남아 있는 병사의 수가 최대가 되도록 하라.

시간복잡도

O(n^2)

이중 for문으로 이중탐색을 하기 때문에 O(n^2) 이다.

알고리즘 : 다이나믹 프로그래밍, LIS

가장 긴 증가하는 부분 수열 LIS의 전형적인 문제이다. 부분 수열의 최대 길이를 매 차례마다 계산하여 dp 배열에 저장하면 된다.

✍️내 소스코드

• dp 배열 : i번째 병사가 마지막인 부분 수열의 최대 길이를 저장한다.
• 두번째 for문에서 i-1번째부터 역순으로 병사를 탐색한다. 전투력이 i번째 병사보다 크면서 부분 수열의 최대 길이가 가장 큰 수를 구한다. 구한 값을 dp배열에 갱신한다.
• i번째 병사보다 전투력이 더 큰 병사가 아직 나오지 않은 경우, 부분 수열의 최대 길이를 1로 설정한다.

전체 코드

  import sys
  si = sys.stdin.readline

  n = int(si())
  seq = list(map(int, si().split()))
  dp = [1] + [0] * (n - 1)

  for i in range(1, n):
    for j in range(i-1, -1, -1):
      if seq[j] > seq[i]:
        dp[i] = max(dp[i], dp[j] + 1)
    if dp[i] == 0:
      dp[i] = 1

  print(n - max(dp))