[BOJ/Gold 5] 백준 28070 유니의 편지 쓰기(C++)

문제 링크

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

28070번: 유니의 편지 쓰기

 

문제

남중 남고를 나온 유니는 주변에 군인인 친구들이 많다. 그런 유니는 군대에 있는 친구들에게 편지를 써 주려 한다.

하지만 편지를 써 줄 친구들이 많아 귀찮은 유니는 오직 한 달 동안만 편지를 쓰기로 한다.

한 달 동안만 편지를 쓰면 군대 안에서 편지를 받지 못하는 친구들도 있으므로, 가장 많은 친구가 군대에 있는 한 달을 찾으려 한다.

머리가 좋지 않아 그 한 달이 언제인지 모르는 유니를 위해 언제 편지를 써야 하는지 구해주자.

입력

첫 번째 줄에 군대에 가는 유니의 친구 수 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄부터 N개의 줄에는 유니의 친구의 입대 시기와 전역 시기가 YYYY-MM 형식으로 주어진다.

YYYY는 연도를 뜻하며 2000 이상 9999 이하의 정수를 나타낸다.

MM는 월을 뜻하며 1 이상 12 이하의 정수로 한 자리 수는 앞에 0을 붙여 나타낸다.

단, 입대 월과 전역 월에는 유니의 친구가 군대에 있으며, 전역 월은 입대 월보다 항상 같거나 더 뒤이다.

출력

유니가 편지를 써야 할 시기를 YYYY-MM 형식으로 출력한다. 편지를 써야 할 시기가 여러 개일 경우, 가장 앞선 시기를 출력한다.

예제 입력 1

4
2023-02 2023-04
2023-03 2025-03
2023-04 2025-02
2024-02 2026-02

예제 출력 1

2023-04

알고리즘 분류

• 누적 합

풀이

주어진 날짜의 정보가 2023-02 2023-04라면, 2023년 2월, 3월, 4월까지 군생활을 한다는 뜻이 된다. 2000년 1월을 1이라고 하면 2023년 2월은 278이 된다. 따라서 DP[278]을 1 증가시키고 DP[281]를 1 감소시킨다.

이렇게 하면 278부터 280까지, 즉 2023년 2월에서 2023년 4월까지 군생활을 하는 사람을 1명 추가한 것이다.

이런 식으로 N명의 사람들의 군 복무 정보를 입력받아 월별로 군샐활을 하는 사람의 수를 기록한다.

이후 월별로 얼마만큼의 친구가 복무하는지를 파악하면서 가장 많이 복무하는 월 중 가장 빠른 월을 YYYY-MM 형태로 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 100001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int DP[MAX], Sum[MAX];
string A, B;
int Max = -1;
int Answer;

int parsing(string S) {
    int Year = stoi(S.substr(0, 4));
    int Month = stoi(S.substr(5));
    return ((Year - 2000) * 12 + Month);
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A >> B;
        DP[parsing(A)]++;
        DP[parsing(B) + 1]--;
    }
}

void settings() {
    for (int i = 1; i < MAX; i++) {
        Sum[i] = Sum[i - 1] + DP[i];
    }
    for (int i = 0; i < MAX; i++) {
        if (Max < Sum[i]) {
            Max = Sum[i];
            Answer = i;
        }
    }
}

void find_Answer() {
    if (Answer % 12 == 0) {
        cout << (Answer / 12) + 1999 << "-12";
    }
    else {
        cout << (Answer / 12) + 2000 << "-";
        if (Answer % 12 < 10) {
            cout << "0";
        }
        cout << Answer % 12 << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}