알고리즘 :: 백준 :: DP :: 18353 :: 병사 배치하기

Embedded June·2020년 9월 20일
1

알고리즘::백준

목록 보기
55/109

문제

문제 링크

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

문제접근

  • 한 가지 아이디어를 떠올리지 못하면 상당히 접근하기 까다로운 문제다!
  • 이 문제는 LIS(최장 길이 부분수열)와 똑같은 문제다.
  • 수열의 가장 앞부터 시작해서 내림차순이 성립하는 부분수열의 길이를 메모이제이션 하는 방식으로 푼다.
  • LIS는 O(N2)O(N^2) 풀이법과 O(NlogN)O(NlogN) 풀이법이 있으나, 1N2,0001 \leq N \leq2,000이므로 간단하게 작성할 수 있는 O(N2)O(N^2) 풀이법을 사용해서 풀고자 한다.
0123456
151148524
1211111
  • i = 1: 15 > 11이므로 i번째 요소는 2
0123456
151148524
1231111
  • i = 2: 15 > 4이고 11 > 4이므로 3
0123456
151148524
1233111
  • i = 3: 15 > 4이고 11 > 4이나 4 < 8이므로 3
0123456
151148524
1233411
  • i = 4: 15 > 4이고 11 > 4이고 8 > 5이므로 4
0123456
151148524
1233451
  • i = 4: 15 > 4이고 11 > 4이고 8 > 5 이고 5 > 2 이므로 5
0123456
151148524
1233455
  • i = 4: 15 > 4이고 11 > 4이고 8 > 5 이고 5 > 4 이므로 5

코드

// https://www.acmicpc.net/problem/18353
#include <iostream>
using namespace std;

int N, soldier[2000], memo[2000];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> soldier[i];
    
    int answer = N;
	// O(n^2) LIS 해결법: 최대 내림차순 수열 길이 찾기
    for (int i = 1; i < N; ++i)
        for (int j = 0; j < i; ++j) {
            if (soldier[j] > soldier[i])
                memo[i] = max(memo[i], memo[j] + 1);
            answer = min(answer, N - memo[i] - 1);
        }
    if (answer == N) cout << "0\n";
    else cout << answer << '\n';
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글