koitp SDS_TEST_CONSULTING 전화상담

문제 링크입니다: https://koitp.org/problem/SDS_TEST_CONSULTING/read/

A 난이도였음에도 불구하고 정답률이 2%일 정도로 구현하기 난해했던 문제였습니다.

저도 펭로그(http://penglog.tistory.com/2)님 덕분에 풀 수 있었습니다.

알고리즘은 다음과 같습니다.

1. 전화 상담을 진행할 때 최소 고객 수와 최대 고객 수를 파악합니다.

i)최소 고객 수는 모든 고객을 순차적으로 원하는 상담시간만큼 상담해줄 경우입니다.

ii)최대 고객 수는 모든 고객을 K분 즉, 최소 상담시간만큼 상담해줄 경우입니다.

2. 최소 고객 수 ~ 최대 고객 수만큼 반복문을 돌립니다.

3. 2번을 진행하는데 우선 현재 고객 수만큼 10점을 곱해주고 최소 상담 시간인 K분만큼은 상담해줬을테니 근로시간에서 (K * 현재 고객 수)를 빼줍니다.

4. 우선은 현재 고객 수들을 모두 K분만 통화했다고 가정했으므로 점수에서 패널티를 모두 빼줍니다.

5. 그리고 현재 상담한 고객 중 패널티가 3점인 고객님들이 원하는만큼 상담하지 못한 시간, 패널티가 2점인 고객님들이 원하는만큼 상담하지 못한 시간, 패널티가 3점인 고객님들이 원하는만큼 상담하지 못한 시간을 구합니다.

6. 그리디(Greedy)하게 접근하면 패널티가 높은 고객들을 최대한 많이 상담해줘야합니다.

i)따라서, 우선 패널티가 3점인 고객들을 최대한 상담해주고 점수를 그만큼 올려줍니다.

ii) i)를 진행하고도 시간이 남는다면 패널티가 2점인 고객들을 최대한 상담해주고 점수를 그만큼 올려줍니다.

iii) ii)를 진행하고도 시간이 남는다면 패널티가 1점인 고객들을 최대한 상담해주고 점수를 그만큼 올려줍니다.

a) iii)를 진행하고도 남은 시간이 K분 이상이면 문제 조건에 따라 다음 고객을 상담해줍니다.

b) iii)를 진행했을 때 남은 시간이 K분 미만이면 최대 점수를 업데이트해줍니다.

*문제 자체는 구현하기 쉽지만 제한시간 내에 AC를 받기는 힘들었던 문제였습니다.

*따라서 핵심은 여태까지 상담한 고객들이 만족하지 못한 시간들을 time1, time2, time3에 저장해 놓는 것이 핵심이였습니다!

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000 + 1;

 

pair<int, int> customer[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int i = 1; i <= test_case; i++)

        {

                 int N, K, L;

                 cin >> N >> K >> L;

 

                 //고객 정보 입력(시간, 패널티)

                 for (int j = 0; j < N; j++)

                         cin >> customer[j].first >> customer[j].second;

 

                 //각 고객을 K분만 응대할 경우: 최대 고객 수

                 int maxCustomer = min(N, L / K);

                

                 //모든 고객을 끝까지 응대할 경우: 최소 고객 수

                 int minCustomer = 0, sum = 0;

                 for (int j = 0; j < maxCustomer; j++)

                 {

                         sum += customer[j].first;

                         if (sum < L)

                                 minCustomer++;

                         else

                                 break;

                 }

 

                 int score = 0, result = 0;

                 int customerIdx = 0;

                 int time1 = 0, time2 = 0, time3 = 0;

                 for (int j = minCustomer; j <= maxCustomer; j++)

                 {

                         //일단 10점씩 합산

                         score = 10 * j;

                         //K분씩 통화했다고 가정하고 근로시간에서 뺀다

                         int remain = L - K * j;

 

                         //(0 ~ j - 1) 번째 고객까지의 누적 패널티 계산하기 위해 통화 안한 시간 계산

                         for(;customerIdx<j; customerIdx++)

                                 switch (customer[customerIdx].second)

                                 {

                                 case 1:

                                          time1 += (customer[customerIdx].first - K);

                                          break;

                                 case 2:

                                          time2 += (customer[customerIdx].first - K);

                                          break;

                                 case 3:

                                          time3 += (customer[customerIdx].first - K);

                                          break;

                                 }

 

                         //패널티 계산

                         score -= (time1 + time2 * 2 + time3 * 3);

 

                         //여태까지 통화한 고객 중에 패널티가 높은 순으로 더 통화해준다

                         //패널티가 3점인 고객들을 다 통화해주고도 시간이 남는 경우

                         if (remain > time3)

                         {

                                 score += time3 * 3;

                                 remain -= time3;

                         }

                         //패널티가 3점인 고객들을 다 통화해주지 못할 경우 최대한 통화해준다

                         else

                         {

                                 score += remain * 3;

                                 result = max(result, score);

                                 continue;

                         }

 

                         //마찬가지로 패널티가 2점인 고객들을 응대

                         if (remain > time2)

                         {

                                 score += time2 * 2;

                                 remain -= time2;

                         }

                         else

                         {

                                 score += remain * 2;

                                 result = max(result, score);

                                 continue;

                         }

 

                         //여태까지 패널티가 3점, 2점인 고객들을 응대했고

                         //패널티가 1점인 고객들을 응대하고도 시간이 남는 경우

                         if (remain > time1)

                         {

                                 score += time1;

                                 remain -= time1;

                                  //K 이상으로 남은 시간이 있다면 다음 고객을 응대

                                 if (remain >= K)

                                          continue;

                         }

                         //패널티가 1점인 고객들을 모두 응대하지 못하는 경우

                         else

                                 score += remain;

                         //최대 점수 업데이트

                         result = max(result, score);

                 }

                 cout << "#" << i << " " << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~