알고리즘 :: 백준 :: DP :: 14501 :: 퇴사

Embedded June·2020년 9월 20일
0

알고리즘::백준

목록 보기
54/109

문제

문제 링크

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

문제접근

  • 이미 본 velog에서 같은 문제를 bruteforce로 푸는 방법을 다뤘다.
    https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-14501-퇴사
  • 푸는 방법은 동일하다. 그저 DP를 사용하므로 bruteforce보다는 빠르게 답을 구할 수 있다.
    • 그 마저도 이 문제는 메모이제이션 배열을 사용하지 않기 때문에 bruteforce와 시간복잡도가 거의 같다.
    • 임의의 날짜를 선택하는 경우선택하지 않고 다음 날로 넘어가는 경우가 존재한다.
      • Base condition 1. 범위를 초과하는 경우
      • Base condition 2. 현재 날짜의 상담을 선택할 수가 없는 경우

코드

// https://www.acmicpc.net/problem/14501
#include <iostream>
using namespace std;

static int N, memo[15];
static pair<int, int> sched[15];

int solve(int day) {
    if (day >= N) return 0;	// [기저]: 범위 초과
    if (day + sched[day].first > N) return solve(day + 1);	// [기저]: 다음 날로 넘어갈 수 밖에 없는 경우.
    if (memo[day] != 0) return memo[day];   // [기저]: 이미 메모이제이션 된 값.
    // 해당 날짜를 택하는 경우와 택하지 않고 넘어가는 경우를 나눠서 계산한다.
    return memo[day] = max(sched[day].second + solve(day + sched[day].first), solve(day + 1));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> sched[i].first >> sched[i].second;
    cout << solve(0) << '\n';
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글