나무 막대( BOJ 7344 )

문제 : https://www.acmicpc.net/problem/7344

7344번: 나무 막대

 

문제 파악하기

N개의 나무 막대를 가공하기 위해 필요한 세팅 횟수를 구하는 문제입니다. 나무 막대는 길이(l)와 무게(w)를 가지고 있으며, 이전에 가공했던 나무 막대보다 길이와 무게 모두 크거나 같다면 세팅할 필요가 없습니다. 따라서, 한번 세팅하면 더 이상 세팅할 필요가 없는 나무 막대들을 찾는 알고리즘이 필요합니다. 알고리즘을 통해 세팅이 필요없는 나무 막대들을 골랐다면, 해당 나무 막대들을 제거하면서 모든 나무 막대들이 제거되기 전까지 총 반복되는 횟수를 구하면 우리가 찾는 정답이 나옵니다. 좀 더 자세한 방법을 살펴보겠습니다.

 

문제 해결하기

우선, 나무 막대는 총 2가지 속성을 가지고 있습니다. 우리는 나무 막대의 2가지 속성인 길이(l)와 무게(w)를 모두 비교해야 하지만 문제 상황을 좀 더 쉽게 만드는 방법이 있습니다. 바로, 길이를 기준으로 나무 막대를 정렬하면 됩니다. 정렬 시, 앞에 있는 나무 막대는 항상 뒤에 있는 나무 막대보다 길이가 크거나 같습니다. 그렇기에 우리는 정렬 후에는 길이는 무시하고 무게만 비교해서 나무 막대의 가공 여부를 확인하면 됩니다.

 

그럼 무게를 어떻게 비교해야 최적으로 나무 막대들을 가공할 수 있을까요? 바로, 세팅이 필요없는 나무 막대가 나오면 바로 가공해주면 됩니다. 뒤에 있는 나무 막대들은 현재 나무 막대에 영향을 미치지 않기에 만약 지금 확인하는 나무 막대가 세팅 없이 가공할 수 있다면 바로 가공하면 됩니다. 그리고 가공한 나무 막대를 제거해주어 다음 탐색에 영향을 미치지 않게 만들면 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <utility>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PAIR;
 
int T, N;
int l, w, ret;
vector< PAIR > inp;
 
list< int > weight;
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // 초기화
        ret = 0;
        inp.clear();
        
        
        // 입력
        scanf("%d", &N);
        for(int i=1;i<=N;i++) {
            scanf("%d %d", &l, &w);
            inp.emplace_back(l, w);
        }
        
        sort(inp.begin(), inp.end());
        for(int i=0;i<N;i++) weight.push_back(inp[i].second);
        
        // 가공할 수 있는 나무 막대를 찾아서 삭제하기
        while(!weight.empty()) {
            int vmin = -10000;
            for(auto t=weight.begin();t!=weight.end();) {
                if(vmin <= *t) {
                    vmin = *t;
                    t = weight.erase(t);
                }
                
                else t++;
            }
            
            ret++;
        }
        
        // 출력
        printf("%d\n", ret);
    }
}
 

후기

리스트를 활용했지만 멀티셋을 사용해서 O(N)으로 해결할 수 있습니다. lower_bound( )를 사용해 현재 나무 막대를 가공할 수 있는 가장 작은 나무 막대의 무게를 수정해주면 됩니다. 정렬과 그리디 알고리즘을 복합적으로 연습할 수 있는 좋은 문제라고 생각합니다.