[백준 15486] 퇴사 2(C++)

퇴사

링크: https://www.acmicpc.net/problem/15486

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
T[i]	3	5	1	1	2	4	2
P[i]	10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

---

문제 접근

• 현재 날짜에 진행되는 상담을 신청할 때, 가장 기댓값이 높은 상담에 현재 값을 더해야 한다.
• 퇴사https://www.acmicpc.net/problem/14501 문제는 O(N^2)으로 간단하게 풀이할 수 있다.
  • 테이블 D를 두고 각 날짜에 들을 수 있는 상담의 최댓값을 저장한다.
  • 이전 값들을 비교하여 가장 큰 값을 찾아 현재 값과 더한다.
  • 비교할 상담의 T값이 현재 시간에 들을 수 없는 상담이라면 Pass한다.
  • 주어진 날짜 N에 들을 수 없는 상담이라면 Pass 한다.
  • D는 {10, 20, 10, 10+20, 10+20+15, -, -}가 되어 45를 구할 수 있다.
• 위 문제의 조건 N은 제한이 15인 데에 반해 해당 문제는 1,500,000 이기 때문에 같은 방식으로는 풀 수 없다.
  • 값을 저장하거나, 오름차순으로 만들어 탐색의 수를 줄여야 한다고 생각했다.
  • 오름차순은 큰 의미가 없기 때문에 값 저장의 방식을 선택했고, 어떤 값을 어떻게 저장할지 생각해보았다.

풀이 힌트

• O(N)에 찾을 수 있는 방법이 있다.
• 현재 날짜에 상담을 들을 수 있는 가장 큰 value를 구해놓으면 된다.
• 해당 값들을 담을 selectable 테이블을 두고 N까지의 값을 구하면 selectable[N]의 값으로 답을 구할 수 있다.
  i의 값에 따라 순서대로 나타내면 아래와 같다.

코드

#include <iostream>

using namespace std;
enum{T, P};

int N, mx;
int counsel[1500001][2];
int selectable[1500001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    for (int i = 1; i <= N; ++i) {
        cin >> counsel[i][T] >> counsel[i][P];
    }
    for (int day = 1; day <= N; ++day) {
        int potential = day + counsel[day][T] - 1;
        // 현재 선택할 수 있는 값 중 가장 큰 값을 가져온다.
        // selectable에서 유효한 값이 10 밖에 없는 경우
        // {10, 0, 0, 0, 0, 0, 0} 이 예상되는 경우 {10, 10, 10, 10, 10 ...} 으로 초기화 해주며 진행
        if (selectable[day] < selectable[day - 1])
            selectable[day] = selectable[day - 1];
        // 현재 선택할 수 있는 값 중 가장 높은 값을 더한다.
        // 오늘 상담 선택할 시 받는 기댓값과 이미 이전 날짜에 의해 초기화 되어있는 값과 비교한다.
        if (potential < N + 1 && selectable[potential] < selectable[day - 1] + counsel[day][P])
            selectable[potential] = selectable[day - 1] + counsel[day][P];
    }
    cout << selectable[N];
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.