백준 14269 (C++) 전설의 쌍검 용사

최초 업로드: 2025-10-02 00:56:10

최근 수정 시간: 2025-10-02 00:56:10

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 전설의 쌍검 용사

[문제 링크](https://www.acmicpc.net/problem/14269)

## 문제 설명

남규나라의 공주 Acka가 마왕한테 납치당했다. 남규나라의 왕 zych는 전설의 쌍검 용사 nein에게 공주를 구해 달라고 부탁하였다. nein은 마왕성에 쳐들어가기 위해 준비를 하고 있는데, nein은 평소에 여러 길이의 검들을 들고 다니며, 상대에 따라 그 중 두가지의 검을 한 손에 하나씩 들어 쌍검으로 싸운다.

nein은 남규나라의 정보부로부터 마왕성의 적들에 대한 정보들을 받았다. nein은 전설의 쌍검 용사답게 오랜 경험을 통해 각각의 적들을 어떤 검들로 상대를 하면 이길 수 있을지 알 수 있었는데, 그 정보는 다음과 같다.

오른손에는 정확히 A길이의 검을 사용하고, 왼손에는 B와 C 사이 길이의 검을 사용하면 적을 이길 수 있다.

nein은 공주 Acka를 구하기 위하여, 마왕성의 모든 적을 이길 수 있도록 검을 챙겨가려고 한다. 하지만, 모든 길이의 검을 가져간다면 너무 무거움으로 모든 적을 이길 수 있는 최소 개수의 검만 챙겨가려고 한다. 하지만 그 최소개수를 모르기 때문에 nein은 당신에게 부탁하였다. nein이 공주 Acka를 구할 수 있는 최소 검의 개수를 구하여라.

## 입력

첫째 줄에는 마왕성의 적 n명이 주어진다.(1≤n≤100,000)

다음 n줄에는 적들을 쓰러트리기 위한 값 A,B,C가 주어진다.(1≤A≤1,000,000 , 1≤B≤C≤1,000,000)

## 출력

마왕성의 적을 모두 쓰러트릴 수 있는 최소 검의 개수를 구하시오.

## 풀이
1. 오른손에 들어야 하는 검은 전부 셋에 넣어 놓는다.
2. 왼손에 들어야 하는 검의 범위가 b~c일때, c를 기준으로 오름차순으로 정렬하여 그리디하게 살펴본다.
3. 이때 각 범위 내의 검이 존재하는지 이분 탐색으로 확인하고 없으면 가장 우선순위가 높은 c를 셋에 넣는다.
4. 이제 모든 경우에 대해, 하나의 적에 대해 왼손에 드는 검과 오른손에 드는 검이 동일한 경우를 이분 탐색으로 살펴보고 더 필요한 검을 추가한다.

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

struct element {
 int a, b, c;
 bool operator<(const element e) const {
 return c < e.c;
 }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

set<int> sword;
 vector<element> v;
 while(n--) {
 int a, b, c; cin >> a >> b >> c;
 sword.insert(a);
 v.push_back({a, b, c});
 }
 sort(v.begin(), v.end());

for(auto e : v) {
        auto iter = sword.lower_bound(e.b);
        if(iter==sword.end() || *iter>e.c) sword.insert(e.c);
    }

set<int> extra; // 왼손 오른손 같은검이 필요한 경우
 for(auto e : v) {
 auto iter = sword.lower_bound(e.b);
 if(*sword.lower_bound(e.b)==e.a && (sword.lower_bound(e.a+1)==sword.end() || *sword.lower_bound(e.a+1)>e.c)) extra.insert(e.c);
 }
 cout << sword.size() + extra.size();
}
```