백준 15486번 [퇴사 2](C++) -yes6686- 티스토리

백준 문제 풀이: 15486 [퇴사 2]

---

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

문제 설명:

상담원이 N일 동안 각 날짜에 상담을 진행할 수 있는 경우, 최대 이익을 계산하는 문제입니다. 각 상담은 진행 기간과 이익이 주어지며, 기간이 초과되면 상담을 진행할 수 없습니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1500001]; // dp[i]: i번째 날까지 최대 수익

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int t, p;
    int maxAns = 0;

    for (int i = 1; i <= n; i++) {
        cin >> t >> p;

        // 이전까지의 최대 이익을 현재 위치에 갱신
        dp[i] = max(dp[i], dp[i - 1]);

        // 상담이 끝나는 날이 N+1을 초과하면 무시
        if (i + t <= n + 1) {
            dp[i + t] = max(dp[i + t], dp[i] + p);
            maxAns = max(maxAns, dp[i + t]);
        }
    }

    cout << maxAns << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 각 날짜별 최대 수익을 계산합니다. 현재 날짜에서 상담을 선택할지 말지를 비교하며 최대값을 갱신합니다.
• 구현 세부사항:
  • dp[i]: i번째 날까지의 최대 수익
  • 점화식:
    • 이전까지의 최대 이익을 현재 위치에 반영: dp[i] = max(dp[i], dp[i - 1])
    • 상담을 진행한 경우: dp[i + t] = max(dp[i + t], dp[i] + p)
• 시간 복잡도 분석: O(n)
  • N개의 날짜에 대해 각각 상수 시간 연산을 수행하므로 효율적입니다.

---

결과

주어진 날짜와 상담 스케줄에 맞추어 최대 이익을 정확히 계산합니다. 동적 프로그래밍을 활용해 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!