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

안녕하세요! 오늘은 백준 2457번 "공주님의 정원" 문제를 해결한 과정과 그 과정에서의 사고 흐름을 공유하려고 합니다. 이 문제는 그리디 알고리즘을 활용하여 해결할 수 있는 흥미로운 문제입니다.

문제 분석:
이 문제는 공듀님의 정원에 피어 있는 꽃들의 개화 기간이 주어졌을 때, 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 하기 위해 선택해야 하는 최소한의 꽃의 개수를 구하는 것입니다.

접근 방법:
1. 꽃의 개화 기간을 시작일과 종료일로 정렬합니다.
2. 현재 날짜부터 시작하여 가장 늦게 지는 꽃을 선택합니다.
3. 선택한 꽃의 종료일을 새로운 시작일로 설정하고 과정을 반복합니다.
4. 모든 기간을 커버할 때까지 이 과정을 반복합니다.

 

코드 구현 :

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, res, cur{301};
vector<int> v;

void Solve() {
	while (cur < 1201) {
		if (cur >= v[cur]) {
			cout << 0 << '\n';
			return;
		}
		cur = v[cur];
		res++;
		sort(v.begin(), v.begin() + cur + 1);
	}
	cout << res << '\n';
}

void Init() {
	cin >> N;
	v.resize(1232);
	for (int i = 0; i < N; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		v[a * 100 + b] = max(v[a * 100 + b], c * 100 + d);
	}
	sort(v.begin(), v.begin() + cur + 1);
}

int main() {
	cin.tie(nullptr)->ios_base::sync_with_stdio(false);
	Init();
	Solve();
	return 0;
}

코드 설명:
1. 날짜를 정수로 표현하기 위해 월과 일을 하나의 정수로 변환합니다. (예: 3월 1일 -> 301)
2. vector v를 사용하여 각 날짜에 대해 가장 늦게 지는 꽃의 종료일을 저장합니다.
3. cur 변수를 사용하여 현재 날짜를 추적합니다.
4. res 변수를 사용하여 선택한 꽃의 개수를 카운트합니다.

주요 로직:
1. Init() 함수에서 입력을 받고 데이터를 초기화합니다.
2. Solve() 함수에서 그리디 알고리즘을 구현합니다.
   - 현재 날짜(cur)에서 시작하여 가장 늦게 지는 꽃을 선택합니다.
   - 선택한 꽃의 종료일을 새로운 cur로 설정합니다.
   - 이 과정을 11월 30일(1201)까지 반복합니다.

구현 시 주의사항:
1. 날짜를 정수로 표현하여 비교와 정렬을 쉽게 만듭니다.
2. 현재 날짜에서 피는 꽃이 없는 경우를 처리합니다. (v[cur] <= cur)
3. 정렬을 사용하여 효율적으로 가장 늦게 지는 꽃을 찾습니다.

4. 예를 들어, 5월 8일 부터 11월 30일 까지 피는 꽃이라고 하면 11월 29일에 꽃이 집니다...

    그렇기에 문제 푸실 때 부등호를 어떻게 설정할 지에 대한 고민이 필요합니다!

이 문제는 그리디 알고리즘의 핵심 아이디어인 "각 단계에서 최적의 선택을 하여 전체적으로 최적의 결과를 얻는다"는 개념을 깨닫는 데에 좋은 문제입니다. 

이 문제 해결 과정이 여러분의 알고리즘 학습에 도움이 되었기를 바랍니다. 궁금한 점이나 추가 설명이 필요한 부분이 있다면 언제든 댓글로 남겨주세요!