[코테 스터디] DP, 병사 배치하기

Q34. 병사 배치하기

🐣문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.


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


백준 링크 | https://www.acmicpc.net/problem/18353

🐥풀이

병사 위치를 기준으로 내림차순 배치가 가능한 병사의 최대 수를 dp 테이블에 업데이트 시켜가면 된다.


병사는 해당 위치에 1명씩 서 있으므로 dp 테이블은 전체 1로 초기화 한다.
i번째의 병사를 기준으로, i번째 직전까지 dp 테이블을 돌면서 전투력이 해당 병사보다 전투력이 높은 병사가 존재하는 위치이면, 현 위치 값과 전투력이 높은 병사의 위치 값+1 중 최댓값을 선택하여 dp 테이블을 업데이트 한다. (병사를 추가로 세우므로 +1 해주어야 한다)


식 : dp[i] = max(dp[i], dp[j]+1) : i는 해당 병사의 위치, j는 전투력이 i번째 병사보다 높은 병사의 위치

🐓코드

# 입력값
n = int(input())
sol = list(map(int, input().split()))

# dp 테이블 초기화
dp = [1]*n

for i in range(1,n):
  # 해당 병사 직전 병사까지 돌면서
  for j in range(i):
    # 전투력이 더 높은 병사가 있으면
    if sol[j]>sol[i]:
      # j번 병사 기준 최댓값 + 1과 현최대값 비교
      dp[i] = max(dp[i], dp[j]+1)

# 열외 수 = 전체 수 - 최대병사 수
print(n-max(dp))

⭐2022.05.09

식 세우기 너무 어렵당@.@