[boj : 14501]퇴사

[문제] : https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

[분류] : 다이나믹 프로그래밍(DP),브루트 포스(Brute force)

 

조건 : 

각 상담일 마다 걸리는 기간이 정해져 있으며 남은 날짜(n) 을 넘어가서는 안된다.

금액이 최대가 되어야 한다.

 

과정:

처음 0번 index 부터 남은 날짜(n)을 초과 하지 않는 범위 내에서 dfs를 통해 금액의 합(ans)를 구한다.

 

구현 방법:

유명하고(well known) 기초적인 브루트 포스 문제입니다.

이차원 배열을 사용해 dfs를 이용하였습니다.

일일이 구해보자라는 생각이 들고 재귀 탐색을 이용하여 모든 경우의 수를 구하면 해결 할 수 있습니다.

dfs가 한번 끝나면 그 전의 경우의 금액의 합을 되돌려 놓고 나서 과정을 진행하면 됩니다.(cnt-=day[1][i])

 

 

소스 : 

#include<bits/stdc++.h>
 
using namespace std;
 
int n,cnt,ans;
int day[2][16];
 
void dfs(int x);
 
int main()
{    
    cin >> n;
 
    for (int i = 0; i < n; i++)
        cin >> day[0][i] >> day[1][i];
 
    dfs(0);
 
    cout << ans;
 
    return 0;
}
void dfs(int x)
{
    for (int i = x; i < n; i++) {
        if (n >= i + day[0][i])
        {
            cnt += day[1][i];
            dfs(i + day[0][i]);
            ans = max(ans,cnt);
            cnt -= day[1][i];
        }
    }
    return;
}

 

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다