[C++] 백준(BOJ) - 17258 : 인기가 넘쳐흘러
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
욱제는 세계적인 인기를 자랑하는 월클(World Class) 스타이다! 영선이는 욱제TV 구독자 5조5억명 달성 기념 파티를 준비하고 있다. 영선이는 욱제를 아는 수많은 사람들에게 초대장을 돌렸는데, 초대장을 받은 모든 사람들이 자신이 언제 와서 언제 떠날 것인지 답변을 줬다.
욱제는 월클병에 걸려서 기대에 미치지 않는 인원과 파티를 즐기는 것을 용납하지 않는다. 그래서 욱제는 자신을 제외한 파티 인원이 T명 미만이 되는 순간 파티장에서 나가고, 파티 인원이 T명 이상이 되는 순간 다시 돌아온다. 답변을 정리하던 영선이는 충격적인 사실을 깨달았는데, 파티가 진행되는 동안 T명 이상의 인원이 계속 유지되지 못 한다는 것이다. 그래서 영선이는 급히 자신의 친구들 K명을 부르려고 한다.
영선이의 친구들은 부끄럼이 많아서 욱제 및 영선이의 친구들을 제외한 파티 인원이 T명 이상이 되는 순간 다 같이 파티장에서 나가 버리고 돌아오지 않는다. 또한 파티 인원이 T명 이상이면 영선이의 친구들은 파티장에 들어가지 않는다. 단, 아직 들어오지 않은 영선이의 친구들은 이후 파티 인원이 T명 미만이 되면 파티장으로 들어 갈 수 있다. 영선이는 친구들 각각을 적절한 시각에 투입시켜 최대한 오랫동안 욱제가 파티에 머물도록 하고 싶다. 꼭 K명을 모두 투입시킬 필요는 없다. 영선이는 욱제를 얼마나 오래 파티에 머물게 할 수 있을까?
입력
첫째 줄에 파티가 진행되는 시간 N (1 ≤ N ≤ 300), 파티에 초대한 사람 수 M (1 ≤ M ≤ 300), 영선이의 친구 수 K (1 ≤ K ≤ 300), 욱제가 기대하는 최소의 파티 인원 T (1 ≤ T ≤ M)가 주어진다.
둘째 줄부터 M개의 줄에 걸쳐 각 줄마다 $a_i$, $b_i$가 주어진다. i번째 사람은 시각 $a_i$에 파티에 참여하고, 시각 $b_i$에 파티를 떠난다. ($1 ≤ a_i ≤ N$, $a_i < b_i ≤ N + 1$)
파티가 시작되는 시각은 1을 기준으로 한다.
출력
영선이의 친구들을 파티에 투입시켰을 때 욱제가 파티에 머무를 수 있는 최대 시간을 출력한다.
알고리즘
- DP
풀이
DP를 진행하기 전에 사전 처리를 해야하는 문제
- 문제를 기반으로 특정 범위 생성
- 초대한 사람의 수 M을 cnt[] 배열 안에 담기
- {시간, 현재인원}에 해당하는 구간을 만들기
- dp의 상태값 설정
- dp[idx][남은(투입 가능한) K]
- 재귀함수에는 매개변수에 prev를 추가
- 현재인원의 변동이 +로도 -로도 일어 날 수 있기 때문
- 필요한 인원보다 더 많은 cost를 필요로 한다면 real_cost를 (cost - prev) 만큼 추가
- 이미 충분히 필요한 인원이 존재하는 경우 real_cost는 0이다
- 친구 투입이 가능한 경우
- dp에 v[here].first(시간)을 추가한 것과 아닌 갈래 두 가지를 재귀호출하여 max값 도출
코드
// BOJ - 17258 : 인기가 넘쳐흘러
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int n, m, k, t, from, to, cnt[304], dp[304][304];
vector<pair<int, int>> v; // 파티 구간을 저장하기 위한 벡터 {시간, 현재인원}
int go(int here, int num, int prev)
{
if (here == v.size()) return 0;
if (dp[here][num]) return dp[here][num];
int cost = max(0, t - v[here].second); // {2,0} 일때 cost는 2명 필요
int real_cost = (prev >= cost) ? 0 : cost - prev; // 실제 코스트 {2,0} -> {2,1} 이전에 소모된 친구수를 빼야함
int& res = dp[here][num];
if (num - real_cost >= 0) // 친구 투입 가능
{
return res = max(go(here + 1, num - real_cost, cost) + v[here].first, go(here + 1, num, 0));
}
else return res = go(here + 1, num, 0);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> k >> t;
for (int i = 0; i < m; i++)
{
cin >> from >> to;
for (int j = from; j < to; j++)
{
cnt[j] = min(t, ++cnt[j]); // 최대 T값만큼만 취급
}
}
int tmp = cnt[1];
int _cnt = 1;
for (int i = 2; i <= n; i++)
{
if (tmp != cnt[i]) // 파티 초대한 사람수 변동 생길 때
{
v.push_back({ _cnt, tmp });
_cnt = 0; // 시간 0으로 초기화
tmp = cnt[i];
}
_cnt++;
}
v.push_back({ _cnt, tmp }); // 마지막 구간
cout << go(0, k, 0) << '\n';
return 0;
}
평가
- DP를 사용하기 전에 문제를 기반으로 특정 범위를 생성하는 전처리 과정이 필요한 문제
- {시간, 현재인원}으로 cnt[] 배열의 값을 통해 구간 생성
- 어떻게 K를 구간 second에 배치해야 최대 시간이 나오는가?
- DP를 통해 idx와 남은 K(투입가능한 K)의 상태값을 설정하여 재귀 호출을 통해 정답 도출
