[백준] 18353번: 병사 배치하기 (C++, LIS 풀이)

문제 링크

18353번: 병사 배치하기

---

이번 문제는 저번에 풀이를 올렸던 LIS 2번 문제를 응용해서 풀 수 있는 문제입니다!

열심히 풀어봅시다~

풀이

LIS(DP+이분탐색)을 내림차순으로 풀이하면 됩니다.

내림차순으로 풀이 후에, 열외할 병사를 출력하기 위해 내림차순으로 저장한 배열(seq)의 크기를 n에서 빼주었습니다.

전에 썼던 LIS 2번 문제 와 흐름이 거의 동일하니, 자세한 풀이는 링크를 참고해주세요!

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int power[2001];
int dp[2001];

void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> power[i];

  vector<int> seq;
  seq.push_back(power[0]);
  dp[0] = 1;
  for (int i = 1; i < n; i++) {
    if (seq.back() > power[i]) {
      seq.push_back(power[i]);
      dp[i] = seq.size() - 1;
    } else {
      int st = 0;
      int en = seq.size() - 1;
      while (st < en) {
        int mid = (st + en) / 2;
        // 내림차순으로 체크
        if (power[i] < seq[mid]) st = mid + 1;
        else en = mid;
      }
      seq[en] = power[i];
      dp[i] = en;
    }
  }
  cout << n - seq.size();
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

배운점

• LIS(이분탐색)을 복습했습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!