인프런 커뮤니티 질문&답변

강사님 한번 들어간 친구들은 욱제 및 영선이의 친구들을 제외한 파티 인원이 T명 일때까지는 쭉 있어야하니까 0이 아닐 것 같습니다.

t = 3 일때,

파티 초대 인원 2 + 영선이 친구 2 = 4 되더라도
영선친구를 1명 빼는 것이 아닌 그대로 유지하는 것이 맞는 것 같습니다.

그래서 현재 구간에서 친구를 추가하지 않더라도 0이 영선이 친구들을 이전에 넣었던 친구들 인원을 그대로 계속 넘겨줘야한다고 생각합니다.

예를 들어

input :
5 3 1 3
1 5
1 2
4 5

output :
2

강사님코드:
1
--------------
input 
9 6 3 4
5 7
1 3
1 2
2 3
5 7
5 10

output
7

강사님 코드:
5
-------------
input:
6 2 1 2 
1 3
4 6

output:
4

강사님 코드:
2

지금 알려주신 코드를 입력해도 100점이 나오긴합니다.
아마 추가 테스트케이스 요청이 반영되지 않아서 인 것 같아 그런 것 같습니다.

그러나 제가 문제를 잘 못 이한 것이라면 죄송합니다.

안녕하세요 ㅎㅎ

먼저 좋은 의견 주시며 날카롭게 지적하신것에 대해 감사의 말씀을 드립니다.

예리한 지적이며 해당 부분은 제가 틀린 것 같습니다.

그래서 현재 구간에서 친구를 추가하지 않더라도 0이 영선이 친구들을 이전에 넣었던 친구들 인원을 그대로 계속 넘겨줘야한다고 생각합니다.

-> 음 근데 그냥 계속 넘겨주는 것은 아니구요. 이게 예를 들어 필요한 부분이 4, 5 라고 했을 때는 -> 계속 넘겨주어야 합니다. 5일 때 4를 넘겨 주어야 합니다. 그러나 3이 필요한데 이미 3이 충족될 경우 0을 넘겨주는 등으로 prev가 조정될 필요는 있습니다.

수정된 코드는 다음과 같습니다.

#include<bits/stdc++.h> 
using namespace std;     
int n, m, k, t, a, b, cnt[301], dp[301][301];
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); 
    int real_cost = (prev >= cost) ? 0 : cost - prev;  

    int & ret = dp[here][num]; 
    if(cost == 0)prev = 0;
    if(num - real_cost >= 0){
        return ret = max(go(here + 1, num - real_cost, cost)+ v[here].first, go(here + 1, num, prev));
    }else return ret = go(here + 1, num, prev);  
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n >> m >> k >> t; 
    for(int j = 0; j < m; j++){
        cin >> a >> b; 
        for(int i = a; i < b; i++)cnt[i] = min(t, ++cnt[i]);
    }
    int temp = cnt[1]; 
    int _count = 1; 
    for(int i = 2; i <= n; i++){  
        if(temp != cnt[i]){ 
            v.push_back({_count, temp});  
            _count = 0; 
            temp = cnt[i];
        }
        _count++;
    }
    v.push_back({_count, temp}); 
    cout << go(0, k, 0) << "\n"; 
    return 0;   
}

해당 코드는 오늘내로 반영하도록 하겠습니다.

감사합니다.

강사 큰돌올림.