[Unsolved][C++] 백준 14501 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

1. 서론

 

DP 공부하려고 고른 문제인데... DP로 풀라고 했는데... 못 풀겠는 거임... 그래서 뭐 어떻게 재귀로 비빌라고 했는데... 어떻게 하는지 감은 오는데 코드 돌려보니까 꼭 뭔가 edge값에서 터지는 거임... 그래서 결국 나랑 같은 아이디어로 푼 사람 찾아내서 그거 보고 품... ㅜㅜ

 

2. 문제 풀이

 

상담 일정이 있다. 상담은 n일 하고 1일당 상담에 걸리는 일수와 상담료가 정해져있다. 상담 스케줄을 잡으면 진행하는 기간 동안에는 다른 스케줄을 할 수가 없다. 그래서 n일간 가장 최대 수익을 낼 수 있는 경우를 구하는 문제이다.

 

처음에 생각했던 것.

재귀로 배열을 돌면서 변수에다가 상담일을 계속 더해준다(상담료도) 그러는 동시에 max함수를 써서 최대 상담료 값을 계속 저장하고 변수가 n일이 되면 return 하게 만든다.

그래서 이 방법에 맞춰서 코드를 짰는데... 결과적으로는 잘 안됐다. 이 방법이 틀린게 아니라 이 방법을 제대로 구현을 못해서.

(아직도 수련이 부족함)

 

그래서 이 방법으로 문제를 푼 사람을 구글에서 찾아나섰다.

https://iridescent-zeal.tistory.com/119?category=1261302 

[백준 BOJ][C++]14501번 퇴사 풀이: 브루트 포스 & 재귀

 

코드를 보니까 내가 푼 코드와 80퍼가 흡사했다. 달랐던 부분은 제약조건을 거는 부분... 그 한 끝에서 사고력의 차이가 나는 것이다 ㅎㅎ

 

3. 코드 설명

 

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<pair<int, int> > v;
int answer = 0, n;

void dp(int idx, int p)
{
    if (idx == n - 1 || idx >= n)
    { 
        answer = max(answer, p);
        return;
    }

    for (int i = idx + v[idx].first; i < n; i++)
        if (i + v[i].first <= n)
            dp(i, p + v[i].second);
    
   answer = max(answer, p);
}
int main()
{
    int i, t, p;

    cin >> n;

    for (i = 0; i < n; i++)
    {
        cin >> t >> p;
        v.push_back(make_pair(t, p));
    }

    for (i = 0; i < v.size(); i++)
    {
        if (i + v[i].first > n)
            continue;
        dp(i, v[i].second);
    }

    cout << answer << endl;
}

 

값을 입력받고 상담일 수, 상담료를 페어로 만들어서 배열에 저장한다.

반복문을 돌리는데(1일부터 n일까지 뭘 선택할지 고르기 위해, 모든 경우의 수를 구하려고 다 돌림)

이때 if문... 상담일 수가 n보다 커지면 dp함수를 호출하지 않는다. (난 이거 생각 못했음, 그냥 dp함수 안에서 처리되는 줄)

dp함수에서 재귀를 위해 for문을 돌리는데 이때 범위가 메서드로 들어온 변수(상담 시작일) + 다음 상담 시작일부터 n까지 반복문을 돌린다.(이 범위도 틀림, 이렇게 하고는 싶었는데 생각을 못함) idx(상담일)가 n보다 작거나 같은 경우에만 재귀로 값을 구한다. 이과정을 계속 반복하면서 max함수로 최댓값을 answer에 저장해준다.(돌면서 제일 최댓값이 바뀌어서 저장됨)

그리고 idx가 마지막 상담일이거나 그 값을 넘어섰으면 마지막 값을 max로 돌려주고 메서드를 종료한다.

 

다음에는 좀 떠올려보자^^