백준 18353번 [병사 배치하기](C++) -yes6686- 티스토리

백준 문제 풀이: 18353 [병사 배치하기]

---

문제 링크: https://www.acmicpc.net/problem/18353

문제 설명:

n명의 병사가 전투력을 기준으로 주어졌을 때, 내림차순으로 배치하기 위해 제외해야 할 최소 병사 수를 구하는 문제입니다.

병사의 전투력 배열에서 내림차순 부분 수열의 길이를 최대로 만들고, 전체 병사 수에서 이를 빼면 제외해야 하는 병사 수가 됩니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[2001]; // 병사의 전투력 배열
int dp[2001];  // DP 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 병사의 수 입력

    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 병사의 전투력 입력
    }

    int maxAns = 0; // 최장 내림차순 부분 수열 길이
    for (int i = 0; i < n; i++) {
        dp[i] = 1; // 최소 길이는 1 (자기 자신만 포함)
        for (int j = 0; j < i; j++) {
            if (arr[i] < arr[j]) {
                // 내림차순 조건 충족 시
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxAns = max(maxAns, dp[i]); // 최장 길이 갱신
    }

    // 제외해야 할 병사 수 계산
    cout << n - maxAns;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 동적 계획법(DP)을 사용하여 최장 내림차순 부분 수열(LDS, Longest Decreasing Subsequence)의 길이를 구합니다.
  • 배열의 각 위치에서 이전 값들과 비교하여 DP 배열을 갱신합니다.
• 구현 세부사항:
  • dp[i]는 i번째 병사를 포함한 최장 내림차순 부분 수열의 길이를 나타냅니다.
  • 병사 전투력 배열 arr에서 i번째 병사의 전투력이 j번째 병사보다 작으면 dp[i] = max(dp[i], dp[j] + 1)로 갱신합니다.
  • 최종적으로 전체 병사 수 n에서 maxAns(최장 내림차순 부분 수열의 길이)를 뺍니다.
• 시간 복잡도 분석:
  • 이중 반복문으로 모든 i, j에 대해 조건을 검사하므로 O(n²)의 시간 복잡도를 가집니다.
  • n의 최대값이 2000이므로, O(n²)은 충분히 효율적입니다.

---

결과

주어진 병사의 전투력 배열에 대해 제외해야 할 최소 병사 수를 정확히 계산합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!