[BOJ/백준] 14501 퇴사

● [문제번호 14501] 퇴사

https://www.acmicpc.net/workbook/view/3974

문제집: 알고리즘 중급 1/3 (code.plus)

 

 

● 알아야 할 것

: DFS

: 재귀

 

 

● 풀이 과정

: [530 - 브루트 포스 - 재귀] 문제집에 있는 문제

 

: DFS의 구현형태에서 크게 벗어나지 않지만,

상담을 연속되지 않게 진행하는 경우들을 고려해야한다.

 

: {현재} + {다음 상담까지 빈 공간} + {다음 상담 소요기간} ≤ 퇴사일

이라는 조건을 잘 고려해서 구현했다.

 

: Base Case는 어떻게 구현할 지 고민하였으나

'항상 퇴사전날까지 일하는 것이 최대 상담료인 건 아니다' 이므로

매 재귀마다 확인하게 만들고,

Base Case는 만들지 않았다.

 

 

● 주의 할 것

: 각 배열들의 index를 주의해야한다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// T : 상담을 완료하는데 걸리는 기간
// P : 상담을 했을 때 받을 수 있는 금액
// cost : 각 상담일정의 상담료 순서대로 저장
int T[16], P[16];
vector<int> cost;
int N, sol;

// 조건에 맞는 상담일정 탐색
void consult(int day)
{
    // 지금까지 만든 상담일정의 총 상담료 확인
    int total = 0;
    
    for(int i = 0; i < cost.size(); i++)
        total += cost[i];
    
    if(sol < total)
        sol = total;
    
    // 반복문의 초기값과 조건문에 의해 Base Case없이도 가능
    // 마지막에 추가한 상담일정 다음날부터 확인
    for(int i = day + 1; i <= N; i++)
    {
        // 현재 + 상담소요기간 <= 퇴사일
        if(i - 1 + T[i] <= N)
        {
            // 1. 상담소요기간 추가
            // 2. 상담추가한 날짜로 재귀
            // 3. 상담소요기간 빼기
            cost.push_back(P[i]);
            consult(i - 1 + T[i]);
            cost.pop_back();
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 상담소요기간과 상담료 입력
    for(int n = 1; n <= N; n++)
        cin >> T[n] >> P[n];
    
    // 현재로 부터 시작
    consult(0);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [533 - 브루트 포스 - 재귀 (참고)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	14501	퇴사	https://pirateturtle.tistory.com/313