백준 2457 공주님의 정원

작성일 | In |

Problem : 공주님의 정원

유형 : 그리디

문제 해석

  • 3월 1일부터 11월 30일까지 꽃이 한가지 이상 피어있도록 할떄, 필요한 꽃의 최소 개수를 구하라.

문제 재해석

  • N제한이 10만이다.
  • 꽃을 심을때 최선의 선택을 해보아야 한다.
  • 전수 조사가 불가능하다. 그리디 하게 접근한다.

해결 전략

  • 꽃을 심을때 최선의 선택이란, 꽃을 최소한으로 심는것이다.
  • 꽃을 최소한으로 심는 방법은 다음과 같다.
    • 이전에 심은 꽃이 지기 전에 심는다.
    • 이전에 심은 꽃보다 늦게 진다.
  • 위 조건에 만족하는, 꽃 중 가장 늦게 지는 꽃을 찾아서 심는다.

구현, 설계

  • 해당 꽃이 언제 지는지 기록한다.
    • 같은 날짜에 피는 꽃이 여러개가 있다면, 그중 가장 늦게 지는 꽃만 기록한다.
  • 날짜를 표현하기 위해 월, 일을 숫자로 변경했다.
    • 일을 전부 따져가기 귀찮아서 월 단위는 100, 일 단위는 1로 설정했다.
    • 3월 1일이면 301 이 된다.
  • 301 ~ 501 까지 꽃이 하나 피어 있다면
    • 301 ~ 501에 피는 꽃을 전부 확인한다.
  • 301 ~ 501에 피는 꽃중, 가장 늦게 지는 꽃의 시간이 501 이하라면, 기간내 공백이 생긴다. 오답
  • 301 ~ 501 범위에서 피고, 그중 가장 늦게 지는 꽃 하나만 심는다.
  • 이후 501 부터 가장 늦게 지는 꽃이 지는 시간의 범위 내 꽃을 다시 찾기 시작한다.
  • 가장 늦게 지는 꽃이 1130 이후에 진다면, 해당 꽃 이후에 더 심을 필요가 없다. 정답이다.

주의할 점

  • 3월 31일에 지는 꽃은 3월 30일 까지만 존재한다. 31일에는 없는 꽃이다.

디버깅

  • 같은 시간대에 피는 꽃이 여러개 있는 경우를 고려 하지 않았다.
  • for내 while 문에서 같은 변수 day를 동시에 증가 시켜서, 건너뛰는 날짜가 발생했었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

int day[1300];
int flower[1300];
int n;

int Solve() {

    int n_flower_death = 0, b_flower_death = 301;
    int flower_cnt = 0;
    int day = 101;

    while (day < 1300) {
        while (day <= b_flower_death) {
            n_flower_death = max(n_flower_death, flower[day]);
            if (n_flower_death > 1130) return flower_cnt + 1;
            day++;
        }
        if (n_flower_death <= b_flower_death) return 0;
        
        flower_cnt++;
        b_flower_death = n_flower_death;
    }


    return 0;
}

void Input() {
    cin >> n;

    int s_m, s_d, e_m, e_d;
    for (int i = 0; i < n; ++i) {
        cin >> s_m >> s_d >> e_m >> e_d;

        int s_day = s_m * 100 + s_d;
        int e_day = e_m * 100 + e_d;
        flower[s_day] = max(flower[s_day], e_day);
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    cout << Solve();

    return 0;
}

피드백

  • for내 while에서 같은 변수를 동시에 증감하지 않도록 주의하자.
  • 푸는데 굉장히 오래 걸렸다. 그리디 유형에 약함이 증명되었다.
  • 사실 그리디라는 유형을 알고도 풀었는데도 오래 걸렸다. 연습이 필요하다.