C++ 14501 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

풀 때마다 어려운 점이 생기는 문제이다.

이번에는 경계 처리가 헷갈려서 시간이 오래 걸렸다. 처음에는 DP로 풀었지만 이번에는 완전탐색으로 풀었다. 

 

풀이

1. 모든 가능한 경우의 수를 탐색한다.

예를 들어 1일을 상담한다면 그 뒤로는 가능한 경우는 4일, 5일, 6일과 7일이 있고, 각각을 상담 가능한지 확인한다.

만약 1일과 4일을 상담한다면, 그 다음 가능한 경우는 (1일, 4일, 5일), (1일, 4일 6일), (1일, 4일, 7일)을 문제의 조건과 비교하여 (1일, 4일, 5일)만 상담이 가능한 것을 알 수 있다.

이러한 방식으로 모든 경우의 수를 탐색한다. 

 

2. 각각의 경우에서 최대 금액을 구한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int t[16];
int p[16];
vector<int> days;
int ans;

void dfs(int st) {
    if(st > n+1) { // 새로운 시작점이 n+1보다 크면 범위를 벗어남
        return;
    }

    int tmp = 0;
    for (const auto &day: days) { // 지금까지 추가된 날의 페이를 더함
        tmp += p[day];
    }
    ans = max(ans, tmp);

    for(int i=st; i<=n; i++) {
        days.push_back(i);
        dfs(i+t[i]); // 다음 가능한 일자로 넘어감
        days.pop_back();
    }
}

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

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

    dfs(1);
    cout << ans;
}

처음에 종료 조건 if문 안에서 비용을 구하고 최대값을 갱신하는 방식으로 풀이했으나, 계속 예외 케이스가 생겼다. 

 

풀이를 찾아보니 굳이 if문 안에서 최대값을 갱신해줄 필요가 없다는 것을 알게되어 밖으로 빼주었다.

st >= n+1이 아니라 st > n+1인 이유는 아래 케이스를 분석해보면 알 수 있다. 결론은 st >= n+1로 하면 마지막 10을 더해주지 못한다.

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10