[BOJ][백준] 그리디 알고리즘-17490번: 일감호에 다리놓기

https://www.acmicpc.net/problem/17490

17490번: 일감호에 다리 놓기

문제

학교의 홍보대사를 맡게 된 건 덕이는 건국대학교의 모든 강의동을 신입생들에게 소개해야 한다.

건국대학교 중앙에 위치한 일감호를 따라 한 바퀴를 돌며 모든 강의동을 소개하는 것이 그의 일이지만, 몇몇 구간들이 공사 중이어서 그 구간을 통해서는 갈 수 없는 상황이다. 급한 대로 건 덕이는 호수에 돌을 던져 징검다리를 놓아 길을 만들어보려고 한다.

강의동은 일감호의 둘레에 따라 원형으로 배치돼 있으며, 강의동 양 옆의 강의동은 서로 이웃한다. 또, 원형으로 배치돼 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃한다.

일감호 안에는 와우도라는 섬이 있다. 건 덕이는 한 강의실에서 다른 모든 강의실로 이동할 수 있도록 강의동에서 와우도까지 징검다리를 놓기로 했다. 하지만 건 덕이의 눈에는 K개의 돌밖에 보이지 않는다. 건덕이는 주어진 돌을 활용해서 징검다리를 완성할 수 있을까?

입력

첫째 줄에 강의동의 수 N, 공사구간의 수 M, 건덕이가 가진 돌의 수 K가 공백으로 구분돼 주어진다. 강의동은 1동부터 N동까지 존재한다.

다음 줄에는 강의동에서 와우도까지 놓아야 하는 돌의 개수 S1, S2,..., SN이 공백으로 구분돼 주어진다. 이는 T번째 강의동에서 와우도까지 ST개의 돌을 놓아야 함을 의미한다. 이어서 M개의 줄에 i, j가 주어진다. 이는 i번째 강의동에서 j번째 강의동까지 가는 길이 공사 중임을 의미한다. 이때 입력되는 i, j번째 건물은 이웃한 강의동이다.

출력

건덕이가 가지고 있는 돌을 놓아 모든 강의동을 연결할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

제한

• 3 ≤ N ≤ 1,000,000
• 0 ≤ M ≤ N
• 1 ≤ i, j ≤ N 
• 1 ≤ T ≤ N인 모든 정수 T에 대해 1 ≤ ST ≤ 1,000,000
• 0 ≤ K ≤ 5,000,000,000

 

---

MST의 탈을 쓴 그리디 문제입니다. MST 써도 되긴 한데 구현도 복잡하고 시간이나 공간적으로나 모두 손해입니다. 풀이의 핵심은, 먼저 연결되어있는 섬들을 단위로 묶습니다. 위의 예제에서는 {(1,2), (3,4), (5)} 가됩니다. 여기서 각 단위별로 섬까지 이어지는 최솟값을 구해서 모두 더하면 그것이 정답입니다. 양옆으로 원처럼 둘러져있는 간선들 외에는 모두 중앙의 섬으로밖에 간선이 연결되지 않기 때문에 MST로 접근할 이유가 없습니다. 이를 바탕으로 코드로 옮기기 위해 입력을 바탕으로 모델링을 해야겠죠.

vector<pair<int,int>>v;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a>b&&a!=N)swap(a,b);
        v.push_back({a-1,b-1});
    }
    sort(v.begin(),v.end());

간선의 입력을 (i,j)에서 1 <=j를 유지해주도록 적절히 스왑 해주되, 원의 형태를 띠므로 (N,1) 형태의 입력도 주의해서 받읍시다.

int last=0;
    for(int i=0;i<v.size();i++)
    {
        int minN=INF;
        int left=v[i].first,right=v[i].second;
        for(int j=last;j<=left;j++)minN=min(minN,cost[j]);
        sum+=minN;
        last=right;
    }

본격적인 정답sum을 구하는 반복문입니다. v내에 있는 left, right노드는 끊어진 간선이므로 last~left 간의 구간에서 최솟값을 뽑아내 더한 후, last를 right로 갱신하면 됩니다.

 

하지만 이대로 제출하면 틀릴 겁니다. 빼먹은 것이 무엇일까요?  바로 노드들이 원형으로 되어있다는 겁니다. 원형을 처리하기 위해 last가 0일 때를 따로 조건문을 빼서 계산합시다. 원형 부분을 처리한 전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=987654321;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N,M;
    ll sum=0,K;
    cin>>N>>M>>K;
    vector<int>cost(N);
    for(auto&i:cost)cin>>i;
    vector<pair<int,int>>v;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a>b&&a!=N)swap(a,b);
        v.push_back({a-1,b-1});
    }
    if(M<=1){cout<<"YES";return 0;}
    sort(v.begin(),v.end());
    
    int last=0;
    for(int i=0;i<v.size();i++)
    {
        int minN=INF;
        int left=v[i].first,right=v[i].second;
        for(int j=last;j<=left;j++)minN=min(minN,cost[j]);
        //last==0, 원형이므로 첫 묶음만 따로 처리
        if(last==0&&v.back().second!=0)
        {
            int end=v.back().second;
            for(int j=N-1;j>=end;j--)minN=min(minN,cost[j]);
        }
        sum+=minN;
        last=right;
    }
    
    if(sum<=K)cout<<"YES";
    else cout<<"NO";
}

M <=1 인경우는 모든 노드가 한 묶음인 경우이므로 먼저 처리를 해 YES를 출력하면 됩니다.K와 총합계는 int형의 범위를 넘는 것도 유의합시다.