백준 14501. 퇴사

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

14501번: 퇴사

 

 

n일 중 일을해서 벌수 있는 최대 돈을 구하는 문제이다.

그런데 일들은 걸리는 시간이 정해져있어서 만약에 1일에 주어진일이 2일 걸린다면 다음날의 일은 할수없게 된다.

먼저 위의 조건은 생각하지말고 그냥 일을 할수 있는 모든 조합을 permuation으로 구했다.

 

n일중 하루 일하는 경우:

1 0 0 0 0 0 0  // day1을 일함 
0 1 0 0 0 0 0  // day2를 일함
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1

 

n일중 이틀 일하는 경우:

1 1 0 0 0 0 0  // day1, day2 일함
1 0 1 0 0 0 0  // day1, day3 일함
1 0 0 1 0 0 0
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 1 0 0 0 0
0 1 0 1 0 0 0
0 1 0 0 1 0 0
0 1 0 0 0 1 0
0 1 0 0 0 0 1
0 0 1 1 0 0 0
0 0 1 0 1 0 0
0 0 1 0 0 1 0
0 0 1 0 0 0 1
0 0 0 1 1 0 0
0 0 0 1 0 1 0
0 0 0 1 0 0 1
0 0 0 0 1 1 0
0 0 0 0 1 0 1
0 0 0 0 0 1 1

 

...

 

이렇게 모든 경우의 수를 구하고 조건을 고려해서 

이전일 + 이전일 걸리는 시간이 현재 일수보다 커지면 그 경우는 제외한다.

또 현재일 + 현재일 걸리는 시간이 n보다 커지면 그일도 못하는 일이므로 제외한다.

 

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

int main() {
    int n;
    int T[100];
    int P[100];
    int ans = 0;

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> T[i] >> P[i];
    }


    for(int i = 1; i <= n; i++) {
        vector<int> v;
        v.push_back(-1); // 1일부터이므로 인덱스맞추기 위해
        // v에 들어갈 1의 갯수가 1,2, ... n개로 늘어남
        for(int j = 0; j < i; j++)
            v.push_back(1);
        // v에 들어갈 0의 갯수가 n, n-1, ... , 0개로 줄어듬
        for(int j = 0; j < n-i; j++)
            v.push_back(0);

        do {

            int prev = 0;
            int sum = 0;
            for(int day = 1; day <= n; day++) {
                if(v[day] == 1) {
                    // 이전일 + 이전일걸리는시간이 현재 일수보다 커지면 현재일은 못하는 일
                    if(day < prev + T[prev]) continue;
                    // 현재일 + 현재일걸리는시간이 n보다 크면 현재일은 못하는 일
                    if(day + T[day] > n+1) continue;
                    sum += P[day];

                    prev = day;
                }
            }
            ans = max(ans, sum);

        } while(prev_permutation(v.begin()+1, v.end()));

    }
    cout << ans;



}

 

---

재귀를 이용한 방법.

#include <iostream>
#include <algorithm>
#define MAX 16
using namespace std;

int n;
int T[MAX];
int P[MAX];

int ans = 0;

void solve(int cur_day, int total_money) {
    if(cur_day >= n+1) {
        ans = max(ans, total_money);
        return;
    }

    // 해당날에 상담하고, 해당 상담하는데 걸리는 일수만큼 넘어감
    if(cur_day + T[cur_day] <= n + 1)
        solve(cur_day + T[cur_day], total_money + P[cur_day]);
    // 해당날에 상담하지 않고, 그 바로 다음날로 넘어감
    if(cur_day + 1 <= n + 1)
        solve(cur_day + 1, total_money);

}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> T[i] >> P[i];

    solve(1,0);
    cout << ans;
}