백준 2457
이 문제는 회의실 배정 문제와 비슷한데, 비교해야할 대상이 4개로 나누어져 있어 비교하기 쉽게 만드는 것이 관건이다. 월과 일을 월에 100을 곱하고 일을 더함으로써 mmdd 형태로 만들면 비교하기가 편하다.
그리고 문제에서 원하는 시작하는 날짜보다 빨리 피거나 늦게 지는 꽃들은 301,1201로 맞춰주었다. 지는 날짜를 기준으로 내림차순으로 정렬을 했다.
12월 1일에 지는 꽃들을 기준으로 가장 빨리 피는 꽃을 먼저 시작점을 잡고, 반복문을 돌면서 가장 적게 겹치는 꽃을 찾아야 하는데 예를 들어
꽃이 6월 15일에 폈다면 6월 15일에 진 꽃을 찾는게 베스트이다.
#include<bits/stdc++.h>
using namespace std;
int n;
vector <pair<int, int >>v;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if ((a == 3 && b == 1) || (a <= 2)) {
a = 3; b = 1;
}
if (c == 12) {
d = 1;
}
v.push_back({ c * 100 + d,a * 100 + b });
}
sort(v.begin(), v.end(),greater<>());
int st = 0, en = 1201; // en 이 1201인 이유 처음 시작점을 잡기 위해서
int cnt = 0;
while (en > 301) {
int nen = 1202;
for (; st < n; st++) { // 가장 적게 겹치는 꽃을 찾음
if (en <= v[st].first) {
if (v[st].first == v[st].second) continue;
if (nen > v[st].second) {
nen = v[st].second;
}
}
else break;
}
if (nen == 1202) break; // 못찾았으면 탈출
else {
cnt++;
en = nen;
}
}
if (en == 301) cout << cnt;
else cout << 0;
}
처음에 이중 pair로 잡고 풀다가, 비교하기 힘들어서 구글링을 좀 했다.
합쳐서 생각하면 훨씬 쉬운데... 그걸 못해서 시간이 많이 낭비됐다. 그리고 어떻게 풀지는 감이 잡혔는데, 깔끔하게 코드 구현이 어려움..
효율적으로 푸는 연습을 해야겠다.. ㅠㅠ
Author And Source
이 문제에 관하여(백준 2457), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@supway/백준-2457저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)