BOJ14501 퇴사

최재원·2023년 3월 30일
0

알고리즘

목록 보기
5/5

문제


문제를 읽자마자 brute force 임을 눈치챌 수 있다......
나는 이러한 경우 보통 DFS를 이용한 풀이를 떠올린다 ㅎㅎㅎ,,,,,,,, 간단하게 생각의 흐름을 정리해보면

  1. 일단 저 T, P를 저장할 자료구조는 pair vector를 사용하면 되겠구나(인덱스는 저 일수로)
  2. DFS 함수의 종료조건은 일수 + T 의 값을 이용하면 되겠구나!
  3. 종료되었을 때 최댓값을 업데이트 하는 형식으로 함수를 작성하면 되겠구나

요렇게 3가지를 생각을 해봤고 코드를 작성했다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<pair<int,int>> v;
int N, T, P;
int max_result=0;
bool checklist[20];
int result=0;

void input() {
    cin >> N;
    pair<int, int> p = make_pair(0, 0);
    v.push_back(p);
    for(int i=0;i<N;i++){
        cin >> T >> P;
        v.push_back(make_pair(T, P));
    }
    memset(checklist, false, 20*sizeof(bool));
}

void cal(int cur) {
    if(cur > N){
        max_result = max_result > result ? max_result : result;
    }
    else {
        for(int i=cur;i<=N;i++){
            if(checklist[i] == false && i+v[i].first <= N+1){
                result += v[i].second;
                checklist[i] = true;
                cal(i+v[i].first);
                checklist[i] = false;
                result -= v[i].second;
            }
        }
        max_result = max_result > result ? max_result : result;
    }
}

int main() {
    input();

    cal(1);

    cout << max_result;

    return 0;
}

아 이거는 좀 tmi(?)스러운 내용이긴 한데 나는 코딩할 때 int main~~~ 부터 치는 습관을 가지고 있었는데 이번에 공부하면서 이거를 없애고 필요한 함수부터 차근차근 작성하는 형식으로 바꿔봤다. 나름 이게 흐름도 생기고 괜찮은듯 ㅎㅎ...

어쨌든 코드는 특별한게 없지만 중요한것은 처음에 생각했던 종료조건이 바뀐것!!
사실 이것 때문에 시간을 정말 많이 소비했는데 처음 생각한것 처럼 종료조건을 설정해버리면 음,,, 예를 들어 7일까지 있는 일정이 있다고 가정하고 4일차에 5일이 걸리는 일정이 있다고 하자. 그러면 4일차에 바로 종료가 되버리고 그 다음부터는 고려할 수가 없다. 예를 들어 6일차, 7일차에 각각 하루씩 소모되는 일정이 있다고 해도 고려되지 않고 최대값이 업데이트 되는 현상이 발생하기 때문!!!

그래서 이를 해결하기 위해 갖갖이 방법을 다 써보면서 코드를 수정했고 최종적으로 제일 간단하게 짜본것이 저 코드다. 먼저 for문 내부에 조건문을 추가해서 현재 일정이 추가가 가능한지 살펴보고 추가가 가능할때만 추가하도록!! 그 다음에 for문이 종료되면 그 후에 다시 최대값을 업데이트 하도록 했다. 이거도 역시 위와 같은 경우 때문인데 cur값이 N보다 커지지 않고 for문이 종료될 수가 있다.(반복문 내부에서 어떠한 index에서도 조건을 만족시키지 않는 경우 그대로 for문이 종료되고 max_result는 업데이트 되지 않는다)
-> 요거 반례는 3, 1 5, 3 1, 1 1 요거 입력해보세여!!!! (질문 게시판에 감사함니다 ㅎㅎㅎ)

결론적으로 해결!

profile
최재원짱짱맨

0개의 댓글