[백준] 18353번: 병사 배치하기 | LIM

📚문제

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

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

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

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

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

 

👩‍💻 풀이

이 문제는 이전 결과값이 다음 결과에 영향을 미치는 대표적인 DP 문제이다. 

https://amazelimi.tistory.com/18

동적계획법(DP)

이 문제의 기본 아이디어는 '가장 긴 증가하는 부분 수열' 로 알려진 전형적인 DP 문제의 아이디어와 같다고 한다. 

'가장 긴 증가하는 부분 수열' 문제란, 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다. 

 

점화식은 다음과 같다. 

D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

 

문제 풀이는 다음 순서와 같다. 

1. 먼저, 내림차순 말고 오름차순으로 구할 거기 때문에 reverse 를 통해 병사 테이블을 역으로 만든다. 

2. DP 테이블을 1로 모두 초기화한다. 여기서 DP 테이블의 길이는 병사 수 만큼이다. 

3. 각 원소에 대해서 전투력이 증가하는 방향으로의 부분 수열을 생성한다. 

 

그림으로 보면 다음과 같다. 

모든 병사에 대해서 순서대로 다음과 같은 과정을 거치면 된다. 

코드는 아래와 같다.