BAEKJOON #18353 (DP) - python

nathan·2021년 8월 5일
0

알고리즘문제

목록 보기
29/102

병사 배치하기

출처 : 백준 #18353

시간 제한메모리 제한
1초256MB

문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

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


입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.


출력

첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.


입출력 예시

예제 입력 1

7
15 11 4 8 5 2 4

예제 출력 1

2


풀이

생각

  • 전형적인 LIS(Longest Increasing Sequences) 문제이다.
  • 완전 탐색을 해야하는 문제이다.
  • 처음에 동적 프로그래밍을 생각하기 어려웠다.
  • 답안을 보고도 이해가 어려웠다..

풀이 설명

  • for 문을 두 개 돌면서 가장 바깥쪽 for 문의 현재 인덱스 i가 있는 위치보다 이전에 있는 인덱스들 (j)을 돈다.
  • 만약 i에 위치한 수가 j에 위치한 수보다 작을경우(내림차순이므로 작아야 함)
    • dp[i] = max(dp[i], dp[j] + 1)
    • 위 식의 의미 :
      • dp[i]가 클 경우에는 과거 누적된 병사 수가 많다는 말
      • dp[j]+1이 클 경우에는 새로운 병사가 원래 dp에 추가 된다는 의미

python code(Bottom UP)

# 백준 18353번 병사 배치하기 (DP)
# 남는 병사수 최대로, 내림차순은 유지하면서~ 

from sys import stdin
f = stdin.readline
n = int(f())
soldiers = list(map(int, f().split()))

def solution(n, arr):
    answer = 0
    dp = [1 for _ in range(n)]
    for i in range(n):
        for j in range(i):
            if arr[i] < arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)


        # print(dp)

    return n - max(dp)



print(solution(n, soldiers))
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글