[ 백준 / 2457 ] 공주님의 정원(C++)

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

 

난이도 : 골드 3 
알고리즘 유형 : 그리디  
풀이 시간 : 42분 

문제 풀이 

문제의 조건을 먼저 확인해보면, 

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

라고 명시되어있다. 여기서 우리가 생각해야 할 조건은 2번 조건이다. 정원에 심는 꽃들의 수를 가능한 적게 하며 공주의 요구사항을 만족해아 하기 때문에 우리는 완전탐색, 그리디와 같은 알고리즘을 생각할 수 있다.

문제 조건을 확인해보면, 입력으로 주어지는 꽃이 피고 지는 날짜의 개수가 $N ≤ 100000$으로 주어져있다. 완전탐색을 사용하면 시간초과가 날 것임이 틀림없기 때문에 그리디 알고리즘으로 접근해보자.

 

일단 입력이 `월`과 `일`로 주어지기 때문에, 날짜 비교에 용이하기 위해 `일`로 통일시켜주었다.

int calendar[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int total_days[13] = { 0, };

// 날짜 누적합 구하기
for (int i = 1; i < 13; i++) {
    total_days[i] = total_days[i - 1] + calendar[i];
}

먼저 월 별 날짜를 하드코딩을 통해 저장해 둔 다음, 누적합을 통해 계산해주었다. 여기서 주의해야 할 점은, 1월에는 이전에 날짜가 없기 때문에 `total_days[i - 1]`을 해주어야 한다는 점이다.

 

이후, 날짜 입력이 정렬되어 받아질 것이란 보장이 없기 때문에 `sort()`를 사용해 정렬을 진행해주었다.

 

이제 그리디 알고리즘을 시작해보자.

`일`로 바뀐 배열을 순차 탐색하는데, 나는 `pair<int, int> tmp` 변수를 사용하여 날짜를 관리해주었다. 또한, ans 배열을 stack처럼 활용하였다. 

 

조건 1. 11월 30일이 지난 경우

if (start > total_days[11]) continue;

조건 2. 입력의 시작 날짜가 3월 1일이 지나지 않은 경우, 마지막날이 최대한 늦은 녀석으로 교체

if (start < total_days[2] + 1) {
    if (ans.back().second < end) {
        ans.pop_back();
        ans.push_back({ start, end });
    }
}

조건 3. 꽃의 피고 지는 날이 3월 1일 ~ 11월 30일 안에 존재한다면, `tmp` 변수의 종료날짜와 현재 입력의 종료날짜를 비교하여 종료 시점이 늦은 녀석으로 업데이트하기. 또한, 만약 입력의 시작 날짜가 `ans` 배열의 마지막 값의 종료 날짜보다 커지게 되는 경우, tmp 배열을 push(여기서도 조건을 생각해주어야 함.)

if (ans.back().second < start) {
    // tmp가 ans와 확실히 연결되는지 체크
    // 만약 연결되지 않는다면, 불가능한 경우임
    if (tmp.first > ans.back().second)
        break;
    // 연결되는 경우, 계속 진행
    ans.push_back(tmp);
    if (tmp.second < end)
        tmp = { start, end };
}
else {
    if (tmp.second < end)
        tmp = { start, end };
}

조건 4 .반복문이 다 돌고 난 뒤, `tmp` 변수에 대해서 생각해주어야한다. 왜냐하면 `tmp`가 `ans`배열에 저장되지 못하고 남아있는 경우가 있을 수 있기 때문이다. 

// tmp로 11월 30일이 결정되는지 확인
if (ans.back().second >= tmp.first && ans.back().second < total_days[11] && tmp.second >= total_days[11]) {
    ans.push_back(tmp);
}

 

마지막으로, 꽃을 못심는 경우에 대해 조건문을 걸어주어 출력을 하면 된다.

 

코드

/*
2457. 공주님의 정원

- 꽃은 모두 같은 해에 피어서 같은 해에 진다.
- 하나의 꽃은 피는 날과 지는 날이 정해져있다.
다음의 두 조건을 만족하는 꽃들을 선택하자
1. 공주가 가장 좋아하는 계절인 3 ~ 11월까지는 매일 꽃이 한 가지 이상 피어있도록 한다.
2. 정원이 넓지 않으므로 심는 꽃의 수를 최대한 적게 한다.

선택한 꽃들의 최소 개수 출력

풀이 : 
그리디하게 접근
N <= 100000 
날짜를 일로 통일하자. -> 계산해서 변환해주기
*/

#include <iostream>
#include <algorithm>
#include <vector>
#define INIT cin.tie(0); ios::sync_with_stdio(false);

using namespace std;

int calendar[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int total_days[13] = { 0, };
int n, sm, sd, em, ed;
vector<pair<int, int>> flowers;

pair<int, int> calc(int sm, int sd, int em, int ed) {
	int startSum = 0;
	int endSum = 0;
	// 출발일
	startSum += total_days[sm - 1] + sd - 1;
	endSum += total_days[em - 1] + ed - 1;

	return { startSum, endSum };
}

int main() {
	INIT;

	// 날짜 누적합 구하기
	for (int i = 1; i < 13; i++) {
		total_days[i] = total_days[i - 1] + calendar[i];
	}

	// 입력 받기
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> sm >> sd >> em >> ed;
		// 구한 누적합에 맞게 피는날, 지는날 구하기
		flowers.push_back(calc(sm, sd, em, ed));
	}

	// 3월 1일 이전 꽃들은 언제바뀌든지 상관없다. 그치만 이후로는 쭉 피어있어야 함
	// 꽃 정렬(시작날짜 빠른 순)
	sort(flowers.begin(), flowers.end());

	// 그리디 시작
	vector<pair<int, int>> ans;
	int start, end;
	pair<int, int> tmp = { 0, 0 };
	ans.push_back(flowers[0]);
	for (int i = 1; i < flowers.size(); i++) {
		start = flowers[i].first; end = flowers[i].second;
		// 11월 30일이 지난 경우, continue
		if (start > total_days[11]) continue;

		// 3월 1일이 지나지 않은 경우, 마지막날이 최대한 늦은 녀석으로 선택
		if (start < total_days[2] + 1) {
			if (ans.back().second < end) {
				ans.pop_back();
				ans.push_back({ start, end });
			}
		}
		else {
			// 무조건적으로 연결되어 있어야 한다.
			// 만약 마지막 녀석의 end보다 start가 더 크다면, tmp 업데이트 후 비교하기
			if (ans.back().second < start) {
				// tmp가 ans와 확실히 연결되는지 체크
				// 만약 연결되지 않는다면, 불가능한 경우임
				if (tmp.first > ans.back().second)
					break;
				// 연결되는 경우, 계속 진행
				ans.push_back(tmp);
				if (tmp.second < end)
					tmp = { start, end };
			}
			else {
				if (tmp.second < end)
					tmp = { start, end };
			}
		}
	}
	// tmp로 11월 30일이 결정되는지 확인
	if (ans.back().second >= tmp.first && ans.back().second < total_days[11] && tmp.second >= total_days[11]) {
		ans.push_back(tmp);
	}

	if (ans.front().first > total_days[2] || ans.back().second < total_days[11] || ans.back().second < total_days[3])
		cout << 0 << '\n';
	else
		cout << ans.size() << '\n';


	return 0;
}

배운 점 

최근에 파이썬으로 풀어본 문제여서 이번에는 c++로 도전하였는데, 이전과 마찬가지로 예외 케이스를 찾는 과정에서 애를 먹었다. 문제 특성 상 범위 비교에도 신경을 써야하고, 여러 겹치는 경우가 많아서 그런 것 같다. 문제를 잘 읽고 꼼꼼하게 따져가며 케이스를 직접 만드는 과정을 연습할 필요가 있을 것 같다.