[BOJ] Thread Knots(17976)

[๋ฐฑ์ค€(BOJ)] Thread Knots(17976) C++

๋ฌธ์ œ : BOJ_17976๋ฒˆ Thread Knots

๋ฌธ์ œ ์„ค๋ช…

์ด๋ถ„ํƒ์ƒ‰

n ๊ฐœ์˜ thread๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ์ด thread ํ•˜๋‚˜ํ•˜๋‚˜๋งˆ๋‹ค ์ ์„ ์ฐ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
์ด๋•Œ ์ ์˜ x์ขŒํ‘œ์˜ ๊ฐ„๊ฒฉ์˜ ์ตœ์†Ÿ๊ฐ’์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
์ ์˜ ๋ฒ”์œ„๊ฐ€ 0๋ถ€ํ„ฐ 1000000000์ด๊ธฐ ๋•Œ๋ฌธ์— ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ์ ์˜ ๊ฐ„๊ฒฉ์„ ํŒŒ์•…ํ•˜๊ธฐ๋Š” ์–ด๋ ค์šฐ๋ฏ€๋กœ, ์ด๋ถ„ ํƒ์ƒ‰์„ ์ด์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Solution

์šฐ์„  thread์˜ ๋ฒ”์œ„๋ฅผ ๋ฒกํ„ฐ๋กœ ์ž…๋ ฅ๋ฐ›์€ ๋’ค, ๋ฒกํ„ฐ๋ฅผ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค.
์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌํ•œ ๊ฐ’์„ ์ˆœํšŒํ•˜๋ฉด์„œ ํ˜„์žฌ ์ด๋ถ„ ํƒ์ƒ‰์˜ mid ๊ฐ’์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ตœ์†Ÿ๊ฐ’์œผ๋กœ ๊ฐ thread๋งˆ๋‹ค ์ ์„ ์ฐ์„ ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.
ํ™•์ธ์„ ์œ„ํ•ด์„  ์šฐ์„  ์ฒซ ๋ฒˆ์งธ thread์˜ ์‹œ์ž‘์ ์— ์ฒซ ๋ฒˆ์งธ ์ ์„ ์ฐ์–ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.
์ฒซ ๋ฒˆ์งธ ์ ์ด ์™ผ์ชฝ์˜ ์žˆ์„์ˆ˜๋ก ์ ๋“ค ๊ฐ„์˜ ๊ฑฐ๋ฆฌ์˜ ์ตœ๋Œ“๊ฐ’์ด ์ปค์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
๊ทธ ํ›„ ๋‹ค์Œ thread๋ถ€ํ„ฐ ๊ฐ thread๋ฅผ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค.
์ด๋•Œ ๋งˆ์ง€๋ง‰์œผ๋กœ ์ฐ์€ ์  + mid ๊ฐ’์ด ๋‹ค์Œ thread์˜ ๋ ๊ฐ’์„ ๋„˜์–ด๊ฐ€๋ฉด ์„ฑ๋ฆฝํ•˜์ง€ ์•Š์œผ๋ฏ€๋กœ ๋‹ค์‹œ right ๊ฐ’์„ ๋‚ฎ์ถ”๊ณ  ๋‹ค์‹œ ์ด๋ถ„ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.
๋งŒ์•ฝ ๋‹ค์Œ thread์˜ ๋ ๊ฐ’ ๋ณด๋‹ค ๋งˆ์ง€๋ง‰์œผ๋กœ ์ฐ์€ ์  + mid ๊ฐ’์ด ์ž‘๋‹ค๋ฉด, ๋งˆ์ง€๋ง‰ ์  + mid ๊ฐ’๊ณผ ๋‹ค์Œ thread์˜ ์‹œ์ž‘ ์  ์ค‘ ์ตœ๋Œ“๊ฐ’์˜ ์œ„์น˜์— ๋‹ค์Œ ์ ์„ ์ฐ๊ณ  ๋‹ค์‹œ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค.
๋˜ ํ•œ ๊ฐ€์žฅ ํฐ ์ ์ด 1000000000์ด๊ธฐ ๋•Œ๋ฌธ์— mid ์—ฐ์‚ฐ์—์„œ int ๊ฐ’์„ ๋„˜์–ด๊ฐˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ long longํ˜•์œผ๋กœ ์„ ์–ธํ•ด ์ค๋‹ˆ๋‹ค.


Description

  • ๋ฒกํ„ฐ ๊ฐ’์€ sort๋กœ ์ •๋ ฌํ–ˆ์Šต๋‹ˆ๋‹ค.
  • pair๋ฅผ sort๋กœ ์ •๋ ฌ ์‹œ, pair์˜ ์ฒซ ๋ฒˆ์งธ ๊ฐ’ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ๋ฉ๋‹ˆ๋‹ค.
  • ํ•ด๋‹น mid ๊ฐ’์ด ์„ฑ๋ฆฝํ•˜๋Š”์ง€๋Š” isBossible ํ•จ์ˆ˜์—์„œ ํ™•์ธํ–ˆ์Šต๋‹ˆ๋‹ค.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long n, le, ri,ans;
vector<pair<long long,long long>> adj;
bool isPossible(long long val);
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        long long st,ed;
        cin >> st >> ed;
        adj.push_back({st,st+ed});
        ri=max(ri,st+ed);
    }
    sort(adj.begin(),adj.end());
    while(le<=ri){
        long long mid = (le+ri)/2;
        if(isPossible(mid)) {
            ans=mid;
            le =mid+1;
        }
        else ri = mid-1;
    }
    cout << ans << '\n';
    return 0;
}
bool isPossible(long long val){
    long long now = adj[0].first;
    for(int i=1;i<n;i++){
        if(now+val > adj[i].second) return false;
        else {
            now = max(adj[i].first,now+val);
        }
    }
    return true;
}