[algorithm] 백준 - 퇴사

dfs로 해결했다.
다음 인덱스에 일해야하는 날짜를 더한 값이 일할 수 있는 날보다 작거나 같을 경우
금액을 추가함과 동시에 해당 인덱스에 일해야하는 날짜를 더한 인덱스를 다음 반복문에 방문하도록 했다.

그렇지 않은 경우엔 바로 다음 인덱스를 방문하도록 했다.

if(index + moneyVector[index].first <= moneyVector.size()){
    dfs(index + moneyVector[index].first, sum + moneyVector[index].second, moneyVector);
 }

그리고 인덱스의 위치가 끝에 도달하면 계산했던 총액이 가장 큰 총액인지를 연산한다.

if(index == moneyVector.size()){
       maxMoney = max(maxMoney, sum);
       return;
}

 

전체적인 코드는 이렇다.

// 퇴사
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int maxMoney = 0;
void dfs(int index, int sum, vector<pair<int,int>> moneyVector){
    if(index == moneyVector.size()){
       maxMoney = max(maxMoney, sum);
       return;
    }
    if(index + moneyVector[index].first <= moneyVector.size()){
        dfs(index + moneyVector[index].first, sum + moneyVector[index].second, moneyVector);
    }
    dfs(index + 1, sum, moneyVector);
}
int main(void){
    int count, num, money;
    cin >> count;
    vector<pair<int,int>> moneyVector;
    for(int i = 0; i < count; i++){
        cin >> num >> money;
        moneyVector.push_back({num, money});
    }
    dfs(0, 0, moneyVector);
    cout << maxMoney;
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102908.cpp

jeongdaeun98/algorithm