[BOJ 30049] 영업의 신(풀이, C++)

BOJ 30049 영업의 신 문제에 대한 글입니다.

 

문제 입력은 조금 복잡해 보일 수 있으나 1 ~ N+2번 줄에서 base 입력을 받고, N+3번 줄부터 매출 변경에 관한 입력을 받으며 입력을 받을 때마다 계산하여 답을 출력해 주는 문제입니다.

 

크게 어려운 부분은 없는 구조이나, 관건은 시간복잡도를 잘 맞추는 것입니다.

<단, 각 매장의 직원별 누적 매출액은 항상 서로 다르며 감소하지 않는다.> 조건으로 인하여 구현에 번거로운 부분 없이 편하게 문제를 풀 수 있습니다.

 

초기 입력 부분은 인원 300명에 가게 10000명으로 많아야 300만 정도의 입력을 받지만, N+3번부터 들어가는 계산은 N = 1,000,000 이기에 마지막 부분의 시간복잡도를 잘 고려해서 문제를 풀어야 합니다.

 

저의 초기 코드는 아래와 같은 방식으로 작성했습니다.

  int time;
  cin >> time;

  for (int i = 0; i < time; i++) {
    int employee, market, profit;
    cin >> employee >> market >> profit;
    profitTable[market - 1][employee - 1] += profit;
    maxProfit[market - 1] =
        max(maxProfit[market - 1], profitTable[market - 1][employee - 1]);

    checkBestSeller(employee - 1, isBestSeller, maxProfit, profitTable,
                    marketCount, employeeToMarket);

    dropBestSeller(isBestSeller, maxProfit, profitTable, employeeCount,
                   market - 1, marketToEmployee);
    cout << countBestSeller(isBestSeller) << '\n';
  }

위 코드는 N+3번 줄부터의 매출 변경을 처리하는 부분인데, checkBestSeller로 매출이 변경된 영업사원을 체크하여 영업왕이 되었는지 체크하고, dropBestSeller로 매출이 변경된 매장에 관련된 모든 직원을 체크하여 영업왕에서 탈락한 지 체크하는 방식이었습니다.

 

각 가게별 최대 매출 maxProfit을 기록하고, 각 직원이 담당하는 매장목록인 employeeToMarket과 각 매장별 배속 직원 목록인 marketToEmployee 등을 기록하는 등 계속 최적화하면서 시도해 보았습니다.

그러나 K가 충분히 작은 상황이라면 최적화가 도움이 될 수 있었겠지만 1 <= K <= M으로 각 직원이 연관된 매장이 최대 M까지 될 수 있는 조건에서는 최적화 이전에 근본적으로 잘못된 풀이였습니다.

 

그래서 문제를 다시 분석했습니다. 어떻게 최대한 연산을 줄일지 고민한 결과 각 매장별 현재 매출왕을 기록하고, 매출왕이 되기 위해 필요한 최고 우수 매장 수인 K는 고정되어 있으니, 각 직원이 몇 개의 매장에서 현재 최고 매출을 달성중인지를 각 직원별로 기록했습니다. 그리고 이를 매번 다 O(N)에 걸쳐서 확인해보지 않고, 변동이 일어날 때 해당 값을 O(1)에 수정해 주었습니다.

그리하여 나온 코드는 아래와 같습니다.

int profitTable[10000]
               [300]; // profitTable[i][j] = i+1번 가게에서 j+1번 직원이 낸 매출
int maxProfit[10000];        // n번 가게에서 최대 매출
int bestSellerCount[300];    // 매출왕 수
int marketBestSeller[10000]; // i번 가게의 매출왕

int countBestSeller(int employeeCount, int chargeCount) {
  int count = 0;
  for (int i = 0; i < employeeCount; i++) {
    if (bestSellerCount[i] == chargeCount) {
      count++;
    }
  }
  return count;
}

int main() {
  int employeeCount, marketCount, chargeCount;
  cin >> employeeCount >> marketCount >> chargeCount;

  for (int i = 0; i < employeeCount; i++) {
    for (int j = 0; j < chargeCount; j++) {
      int market, profit;
      cin >> market >> profit;
      profitTable[market - 1][i] = profit;
      maxProfit[market - 1] = max(maxProfit[market - 1], profit);
    }
  }

  for (int i = 0; i < marketCount; i++) {
    if (maxProfit[i] == 0) {
      continue;
    }
    for (int j = 0; j < employeeCount; j++) {
      if (profitTable[i][j] == maxProfit[i]) {
        ++bestSellerCount[j];
        marketBestSeller[i] = j;
        break;
      }
    }
  }

  int tasks;
  cin >> tasks;

  for (int i = 0; i < tasks; i++) {
    int employee, market, profit;
    cin >> employee >> market >> profit;
    market--;
    employee--;

    if (marketBestSeller[market] == employee) {
      profitTable[market][employee] += profit;
      maxProfit[market] = profitTable[market][employee];
    } else {
      profitTable[market][employee] += profit;
      if (profitTable[market][employee] > maxProfit[market]) {
        maxProfit[market] = profitTable[market][employee];
        bestSellerCount[marketBestSeller[market]]--;
        marketBestSeller[market] = employee;
        bestSellerCount[employee]++;
      }
    }

    cout << countBestSeller(employeeCount, chargeCount) << endl;
  }

  return 0;
}

배운 것

단순 구현 문제였지만, 시간 복잡도를 맞추기 위해서는 조건상 최악의 상황에도 통과할 수 있는 알고리즘을 사용해야 한다는 것을 배웠습니다.