BOJ_7983
😭 문제가 나의 상황과 알맞다. 정말 아무것도 하기싫다. 하지만 해야한다.
- 내일부터 연속으로 최대 놀수있는 날을 구해야한다.
- 그러므로 중간중간 노는 날은 무시하고 처음 일을 시작하기 전까지만 구해주면 된다.
- 이말은 즉슨 맨 끝부터 차근차근 일을 하면서 맨 앞까지 오면 된다.
- 입력이 정렬이 되어있지 않으므로 정렬해줘야한다.
- 마감 기한이 가장 큰 것부터
정렬
하고그리디
를 사용해서 풀어주면 될 것으로 보인다.
💻 그리디
sort(v.begin(), v.end(), compare);
int stand = v[0].second - v[0].first;
for (int i = 1; i < N; i++)
{
if(v[i].second < stand)
{
stand = v[i].second - v[i].first;
}
else{
stand = stand - v[i].first;
}
}
- 일이 끝난 날이
stand
, 이 변수를 기준으로- 다음 마감기한 날짜가 더 작으면 마감기한에서 걸리는 시간을 마이너스
: 마감기한까지 끝내줘야 하기 때문에 stand에서 걸리는 시간을 빼면 안된다. - 다음 마감기한 날짜가 더 크거나 같으면? 그냥 stand에서 빼준다.
- 다음 마감기한 날짜가 더 작으면 마감기한에서 걸리는 시간을 마이너스
💻 전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;
#define endl "\n"
vector<pair<int,int> > v;
bool compare(pair<int,int> a, pair<int,int> b)
{
return a.second > b.second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
int day, finish;
cin >> day >> finish;
v.push_back(make_pair(day, finish));
}
sort(v.begin(), v.end(), compare);
int stand = v[0].second - v[0].first;
for (int i = 1; i < N; i++)
{
if(v[i].second < stand)
{
stand = v[i].second - v[i].first;
}
else{
stand = stand - v[i].first;
}
}
cout << stand << endl;
}
Author And Source
이 문제에 관하여(BOJ_7983), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@luck2901/BOJ7983저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)