[백준] 14501번 : 퇴사

문제

 

---

풀이

 

dp로 풀면 더 빨리 풀 수 있을텐데 난 그냥 완전탐색(브루트포스)으로 풀었다.

문제를 풀고 보니 dfs를 사용한 코드가 많았다. 근데 뭔가 논리가 그냥 이대로 dp 쓰면 되는거 아닌가 싶긴 했다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int N, money, result;
vector<pair<int, int>> input;

void backtracking(int idx) {
    if (money > result) //최대 비용 비교
        result = money;
    for (int i = idx; i < N; i++) {
        if ((input[i].first + i) <= N) { //상담 가능
            money += input[i].second; //visited 처리
            backtracking(input[i].first + i);
            money -= input[i].second; //unvisited 처리
        }
    }
}

int main() {
    int dur, profit;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> dur >> profit;
        input.push_back(make_pair(dur, profit));
    }
    backtracking(0);
    cout << result;
}

전체 소스코드다.

 

void backtracking(int idx) {
    if (money > result) //최대 비용 비교
        result = money;
    for (int i = idx; i < N; i++) {
        if ((input[i].first + i) <= N) { //상담 가능
            money += input[i].second; //visited 처리
            backtracking(input[i].first + i);
            money -= input[i].second; //unvisited 처리
        }
    }
}

0일부터 시작하니 오름차순 백트래킹 탐색과 유사하게 코드를 작성했다.

특정 날의 인덱스와 그 날의 상담 소요일을 합한 값이 N보다 작거나 같다면 할 수 있는 상담이니까 visited 처리한다.

 

종료조건을 idx==N일때로 할 순 없었다. 거기까지 도달하지 못하고도 최대 비용을 얻을 수도 있기 때문이다.

그래서 그냥 백트래킹을 호출할 때마다 비교했다.

이 과정에서 의미없이 갱신되는 result의 경우의 수가 그렇게 신경쓸 정도가 아니라고 생각했기 떄문이다.