Algorithm/간격, 라인스위핑

[틀림] [알고리즘] 백준 1911 흙길 보수하기 // 라인스위핑

* 풀이핵심 아이디어변수를 잘 정의해야함. idx 변수 : 현재까지 덮은 위치b : 필요한 널빤지 갯수 = 길이 / m + (길이%m)이 있으면 +1 없으면 + 0크게 3가지 경우로 나누기첫경우 -> pass나머지경우 -> 길이를 계산, idx 갱신#includeusing namespace std; void fastIO(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);} int n; // 웅덩이의 개수int m; // 널빤지의 길이int idx; // 현재까지 덮은 위치int ret; // 필요한 널빤지의 총 개수int b; // 현재 웅덩이를 덮는데 필요한 널빤지 개수int main(){ fa..

[맞음?] [알고리즘] 백준 2170 선긋기 // 라인스위핑은 정렬

https://www.acmicpc.net/problem/2170   #include using namespace std;typedef long long ll;int n,s,e,l,r,ret;pair p[1000000+4];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=0;i>s>>e; p[i]={s,e}; } sort(p,p+n); l=p[0].first; r=p[0].second; for(int i=1;i=p[i].first && r * 25.2.20. 2회독크게 3경우로 나눔포함하는경우,우측이 더 긴경우하나도 안겹치고 새롭게 시작 하는경우#includeusing namespace ..

리트코드 57 삽입간격 c++ // 구현, 라인스위핑은 케이스 분류하라

https://leetcode.com/problems/insert-interval/description/1. 의사코드이때, 핵심은 new를 탐색완료한것중 제일 우측의 간격으로 유지하는 점이다. 2. 전체코드class Solution {public: vector> insert(vector>& intervals, vector& newInterval) { vector> ret; //new에는 현재 탐색완료한 간격중 제일 우측의 간격이 들어있다. for(auto interval : intervals){ if(interval[1]시간복잡도 : O(N) 추정