Brute Force, 퇴사

안녕하세요.

알고리즘 공부하기 정말 ... 좋네요 ...ㅎㅎㅎ

오늘은 백준의 '삼성 SW 역량 테스트 기출 문제' 문제집에 있는 문제 중 하나인 '퇴사'를 가져와보았습니다.

 

이 문제의 해결법을 먼저 말해보자면, Brute Force 알고리즘으로 짜보았어요.

Brute Force는 무식한(brute) + 힘 (force) 라는 의미로, 무식하게 밀어붙인다? 쯤 ...? 인 것 같아요.

완전 탐색 알고리즘으로 모든 경우의 수를 탐색하게 됩니다.

이 알고리즘은 정답만을 출력하기 때문에, 믿을만한 알고리즘이죠.

 

문제는 아래와 같습니다.

 

문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

예제 입력 1
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 입력 1 - 출력 
45

 

저는 사실 이 문제를 보고 Greedy를 먼저 생각했는데요.

왜냐면 Greedy에 대한 내용을 다룰 때 비슷한 문제를 Greedy 예제로 확인했었거든요.

 

이제 코드를 확인해볼게요.

 

#include <iostream>
#include <vector>

using namespace std;
int _max = 0;

void brute(vector<int> t, vector<int> p, int i, int sum) {
    if (i == t.size() && sum > _max) {
        _max = sum;
        return;
    }
    if (i >= t.size()) return;
    if (sum > _max) _max = sum;
    
    brute(t, p, i + 1, sum);
    brute(t, p, i + t[i], sum + p[i]);
}

int main(int argc, const char * argv[]) {
    int k;
    vector<int> t;
    vector<int> p;
    
    cin >> k;
    int i = 0;
    while(i++ < k) {
        int st, sp;
        cin >> st >> sp;
        t.push_back(st);
        p.push_back(sp);
    }
    
    brute(t, p, 0, 0);
    cout << _max;
    return 0;
}

 

입력을 vector에 담은 다음, brute라는 함수를 불러서 재귀를 사용해 최적의 값을 구하고 있어요.

brute 함수에서는  입력값을 담은 Ti, Pi 배열, 재귀 중 진행 위치를 알 수 있게해줄 i (index) 그리고 진행 값을 sum에 담아 해당 경로가 끝나면 sum과 _max(최댓값)을 비교해서 값을 할당하게 만들었어요.

 

i 번째 날을 포함하지 않을 경우 (i+1)와 i 번째 날을 포한하는 경우 (i+T[I]) 로 구성해서 재귀를 진행하면 모든 날들을 다 구할 수 있겠죠?

 

그럼 이번 문제는 여기까지 ,,, 하겠습니다.

더 나은 알고리즘이나 피드백은 언제나 환영입니당 헤헤