[BOJ/Silver 3] 백준 31869 선배님 밥 사주세요!(C++)

문제 링크

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

 

문제

24학번 신입생 정민이는 밥을 사준다는 선배들의 약속을 모두 메모장에 기록해 둔다. 메모장의 각 줄에는 선배 이름 𝑆, 약속 주차 𝑊, 요일 𝐷, 밥 약속에 드는 비용 𝑃가 기록돼 있다. 선배 이름은 문자열, 나머지는 정수로 기록한다. 또, 한 선배는 두 번 이상 밥을 사주지 않으며 모든 선배의 이름은 다르다.

정민이는 컴퓨터학부답게 요일을 0과 6 사이의 정수로 기록한다. 예를 들어 월요일은 0이고 목요일은 3이다.

정민이의 착한 선배들은 밥을 사줄 수 있는 충분한 돈이 있다면 귀여운 후배와의 밥 약속을 무를 수 없다. 정민이의 기록과 선배들이 지닌 돈을 보고 정민이가 최대 며칠 연속으로 밥을 얻어먹을 수 있는지 구해보자!

 

입력

첫 번째 줄에는 기록의 수 𝑁이 주어진다. (0 ≤ 𝑁 ≤ 100)

두 번째 줄부터 𝑁개의 줄에 걸쳐 기록의 정보가 주어진다. 기록의 정보는 𝑆 𝑊 𝐷 𝑃와 같은 형식으로 주어지며, 이는 𝑆선배가 𝑊주차 𝐷번째 요일에 𝑃원이 필요한 밥 약속을 잡았음을 뜻한다. 기록에 있는 선배의 이름은 모두 정확히 한 번씩만 주어진다. (1 ≤ 𝑊 ≤ 10; 0 ≤ 𝐷 ≤ 6; 0 ≤ 𝑃 ≤ 100,000)

그다음 줄부터 𝑁개의 줄에 걸쳐 앞서 주어진 선배 이름과 선배가 소지한 돈 𝑀이 공백을 사이에 두고 주어진다. 여기서 주어지는 선배 이름의 순서는 앞서 주어진 선배 이름의 순서와 다를 수 있다. (0 ≤ 𝑀 ≤ 100,000)

선배 이름은 12글자 이내의 영어 대소문자로 이뤄진 문자열로 주어진다.

 

출력

정민이가 최대 며칠 연속으로 밥을 얻어먹을 수 있는지 출력한다.

 

예제 입력 1

3
OhIkjun 1 6 10000
Hyukjun 1 5 5000
Junseong 2 0 8000
Hyukjun 4000
OhIkjun 12000
Junseong 20000

예제 출력 1

2

 

 

노트

국제 표준으로, 일주일의 시작은 월요일이다.

 

알고리즘 분류

• 구현
• 자료 구조

 

풀이

시간 기준으로 N개의 약속을 오름차순 정렬한다.

첫 번째 약속부터 탐색하며 선배가 그날 밥을 사줬는지 기록한다.

마지막으로 10주 동안 첫째 날부터 마지막 날까지 선배한테 밥을 연속으로 얻어먹은 날의 최댓값을 찾는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct SENPAI {
    string Name;
    int Price;
};

int N, W, D, P;
string S;
vector<pair<int, SENPAI> > Senpais;
unordered_map<string, int> Moneys;
bool Visited[10][7];
int Answer;

bool comp(pair<int, SENPAI> A, pair<int, SENPAI> B) {
    return (A.first < B.first);
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S >> W >> D >> P;
        SENPAI Senpai = { S,P };
        Senpais.push_back(make_pair((W - 1) * 7 + D, Senpai));
    }
    sort(Senpais.begin(), Senpais.end(), comp);
    for (int i = 0; i < N; i++) {
        cin >> S >> P;
        Moneys.insert(make_pair(S, P));
    }
}

void settings() {
    for (int i = 0; i < N; i++) {
        int Week = Senpais[i].first / 7;
        int Day = Senpais[i].first % 7;
        string Name = Senpais[i].second.Name;
        int Price = Senpais[i].second.Price;
        int Money = Moneys[Name];
        if (Money >= Price) {
            Visited[Week][Day] = true;
            Moneys[Name] = -1;
        }
    }

    int Max_Day = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 7; j++) {
            if (Visited[i][j]) {
                Max_Day++;
            }
            else {
                Answer = max(Answer, Max_Day);
                Max_Day = 0;
            }
        }
    }
    Answer = max(Answer, Max_Day);
}

void find_Answer() {
    cout << Answer << "\n";
}

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

    return 0;
}