[백준 31869][구현] 선배님 밥 사주세요!

출제 배경

이 문제 또한 HEPC 2024에서 본인이 출제한 문제이다. 신입생 대상으로 출제한 문제로, 자료구조(map)를 안다면 쉽게 풀 수 있고, 그렇지 않더라도 단순 구현으로도 풀어낼 수 있는 문제이다.
 

문제 설명

문제 링크
map을 사용하면 아주 쉬운 문제이므로, 자료구조를 모른다는 전제 하에 풀이하겠다.

먼저 w주차 d번째 날로 들어오는 약속일자를 첫 날로부터의 몇 번째 날인지로 나타내자. 즉, w*7+d로 나타낼 수 있다. 이렇게 계산해두면 풀이가 더 수월해진다.

이름과 약속일자, 필요한 금액을 입력받을 때 각각 나눠서 같은 인덱스의 배열에 저장하자. 물론 tuple이나 struct 등을 사용해서 한 번에 저장해도 무관하다.

이제 이름과 소지한 돈을 입력받을 때, 이전에 입력받은 이름 배열에서 같은 이름을 찾아 인덱스를 구하고 입력받은 필요한 금액 배열의 해당 인덱스에 위치한 값과 소지한 돈을 비교하여, 만약 사줄 수 없다면 따로 표기한다. 여기서는 소지한 돈을 -1로 표시함으로 표기하였다.

이제 첫 날부터 끝 날까지 선배가 연속해서 사줄 수 있는 일 수를 구하면 된다. 즉, 필요한 금액 배열에서 양수 부분 수열의 최대 길이를 구하면 된다. 범위가 짧기 때문에 브루트포스로 충분히 구할 수 있다.
 

코드

#include <iostream>
#include <string>
using namespace std;

int main()
{
    // 신입생이 푼다고 가정하자.
    // 최대 2차원배열, 다중반복조건문

    int n;
    cin >> n;

    string s[100];
    int w, td, d[100], p1[100];
    for (int i = 0; i < n; i++)
    {
        cin >> s[i] >> w >> td >> p1[i];
        d[i] = w * 7 + td;
    }

    string s2;
    int p2;
    for (int i = 0; i < n; i++)
    {
        cin >> s2 >> p2;
        for (int j = 0; j < n; j++)
        {
            if (s2 == s[j])
            {
                if (p2 < p1[j])
                {
                    p1[j] = -1;
                }
                break;
            }
        }
    }

    /*
    s(이름) d(날짜) p1(밥의가격) p1==-1이면 못사줌
    */

    int max_cnt = 0;
    // 브루트포스
    for (int i = 0; i < n; i++)
    {
        // 시작날짜
        int start_d = d[i];
        // 시작부터 돈없으면 다음으로
        if (p1[i] == -1)
            continue;

        int end_d = d[i] + 1;
        // 끝나는 날짜 서칭
        while (1)
        {
            bool flag = false;
            for (int j = 0; j < n; j++)
            {
                if (d[j] == end_d && p1[j] != -1)
                {
                    flag = true;
                }
            }
            if (!flag)
            {
                break;
            }
            end_d++;
        }
        if (end_d - start_d > max_cnt)
        {
            max_cnt = end_d - start_d;
        }
    }
    cout << max_cnt;
}