문제

나의 요약

N개의 꽃은 모두 같은 해에 피어서 같은 해에 진다.
N개의 꽃 중 두 조건을 만족하는 꽃들을 선택하자.
1. 3/1~11/30까지 매일 꽃이 한가지 이상 피어있도록
2. 정원에 심는 꽃들의 수를 가능한 적게
N개의 꽃 중에서 두 조건을 만족하는 꽃들을 선택할 때, 선택한 꽃들의 최소 개수 출력한다.
만약 만족하는 꽃들이 없다면 0을 출력한다.

접근 방식

예전에 풀었던 문제라 어렴풋이 기억은 났는데, 4년전에 푼 문제라서 잘 기억은 안 났다.
우선 매일 한가지 이상 피도록 하면서, 제일 늦게 지는 꽃들을 선택하면 그것이 최소 개수가 될 것이라고 생각했다.

1. 먼저 3월 1일 이하로 피는 꽃들 중 가장 늦게 지는 꽃을 고른다.
2. 그 다음에는 그 꽃의 지는 날 이하로 피는 꽃들 중 가장 늦게 지는 꽃을 고른다.
3. 2번을 다시 반복해서 지는 날이 11월 30일이 넘어갈 때까지 반복한다.
   3-1. 반복하다가 그 꽃의 지는 날 이하로 피는 꽃들이 하나도 없다면 0을 출력한다.

풀이

#include <bits/stdc++.h>
using namespace std;

int DateToNum(int month, int day)
{
	int num = 0;
	for(int m = 1; m < month; m++)
	{
		if(m == 4 || m == 6 || m == 9 || m == 11)
		{
			num += 30;
		}
		else if(m == 2)
		{
			num += 28;
		}
		else
		{
			num += 31;
		}
	}
	
	num += day;
	return num;
}

int N;
vector<pair<int, int> > flowers;
int bloomMin, bloomMax;

void Input()
{
	cin >> N;
	for(int i = 0; i < N; i++)
	{
		int bloomMinMonth, bloomMinDay;
		int bloomMaxMonth, bloomMaxDay;
		cin >> bloomMinMonth >> bloomMinDay >> bloomMaxMonth >> bloomMaxDay;
		flowers.push_back({DateToNum(bloomMinMonth, bloomMinDay), DateToNum(bloomMaxMonth, bloomMaxDay)});
	}
	sort(flowers.begin(), flowers.end());
}

void Solve()
{
	bloomMin = DateToNum(3, 1);
	bloomMax = DateToNum(11, 30);
	
	int ans = 0;
	int currentBloomStart = 0;
	int currentBloomEnd = 0;
	
	while(currentBloomEnd <= bloomMax)
	{
		bool isSatisfied = false;
		ans++;
		
		for(int i = 0; i < flowers.size(); i++)
		{
			int bloomStart = flowers[i].first;
			int bloomEnd = flowers[i].second;
			
			if(bloomStart <= bloomMin && bloomEnd > currentBloomEnd)
			{
				isSatisfied = true;
				currentBloomStart = bloomStart;
				currentBloomEnd = bloomEnd;
			}
		}
		
		if(!isSatisfied) 
		{
			ans = 0;
			break;
		}
		
		bloomMin = currentBloomEnd;
	}
	cout << ans;
}

int main()
{
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);
  	
  	Input();
  	Solve();
}

우선 DateToNum 함수를 통해 날짜를 하나의 숫자로 변환해준다.

실질적 풀이는 Solve 함수에서 진행이 된다.
위의 접근 방식에서 언급했던 대로, 현재 선택한 꽃의 지는 날을 담고 있는 currentBloomEnd가 11월 30일을 담고 있는 bloomMax 이하일 동안 계속 반복한다.
1. 꽃들을 순회하며 피는 날이 마지막 지는 날 이하인지, 지는 날이 제일 늦는지 확인한다.
2. 둘다 만족한다면, 이 꽃의 피는 날과 지는 날을 저장해둔다.
3-1. 다 순회하고 나서도 조건이 만족하는 꽃이 없었다면 0을 저장하고 끝낸다.
3-2. 하나라도 있었다면 마지막 지는 날을 이번 반복에서 가장 늦게 지는 날로 바꿔준다.

헤맨 지점

단순해 보이는 접근방식과는 다르게 변수가 여러개 쓰이다보니 잠깐 헷갈렸다. 그리디는 접근방식만 알아차린다면 꽤 쉽지만, 그럼에도 여러 변수가 활용될 수 있으니 코드를 작성하기 전 제대로 정리를 하고 들어가자.

여담으로 내가 4년전에 풀었던 풀이도 보았는데, 날짜를 단순히 월*100+일로 처리해 풀었던 것을 보았다.. 아무리 생각해도 이것이 더 간단한 변환 방법 같다. 4년전의 나에게 감탄해버렸다.