AlgorithmBOJ

백준 퇴사 14501

, ,

1. 백준퇴사14501

2. 컴퓨팅 스킬

  • 백트래킹 재귀호출

3. 컴퓨팅 사고

  • 맨 처음에 조합으로 next_permutation을 사용해서 해당 T[i]만큼 false를 만들면서 오는 경우를 찾으면 어떨까 라고 생각하였지만, 직감적으로 쉽지않다는것을 느꼈습니다. 그래서 재귀함수로 풀어보자 라는 생각으로 풀게되었습니다.
  • 이 부분이 가장 중요한 부분입니다. 재귀 백트래킹으로 idx==n+1과 같을때 basement 정답을 찾았을 경우를 확인하였습니다. 그리고 idx값이 n+1보다 클 경우 조건에 퇴사할 수 없으므로 return으로 종료시켜주었습니다.
  • 기존것과 다르게 이것은 선택할지 말지에 대한 경우를 잘 확인해주어야합니다. 예를 들면, [1,2,3,4,5]라는 T배열이있다고 가정하면 1,2,3,4,5라는 값을 모두 사용하는것이 아니라 날짜가 n+1과 같은경우를 찾는 경우이기 때문에 1,2,3,4,5라는 값을 모두 사용할 수 있고, 최소 하나이상의 값만 사용할 수 있습니다.
  • 너무 습관적으로 for문안에다가 재귀함수를 호출하였는데, 이 문제는 조합이나 순열문제가 아니라 말그대로 브루트포스문제였습니다. for을 작성하게 되면 1,2,3,4,5의 모든 값에 대한 경우의 수를 확인하는것입니다. 익숙함에 속아버렸습니다.
  • dfs를 호출할때 이것도 무의식적으로 dfs(0,0)을 호출하였는데, 문제의 조건에서 보면 최소 1일부터이기 때문에 초기조건을 1부터 시작하였습니다.idx는 상담일 day와 같습니다.
  • 최대값을 찾아주는것은 max_num이라는 변수를 활용하여서 그때마다 비교해서 업데이트를 해주었습니다. max_elements를 사용할 수도 있었지만, 빠르게 비교해주기위해서 이런 로직을 사용하였습니다.

4. 풀이

4.1. 백트래킹 DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

//
//  11_백준_퇴사_14501.cpp
//  algorithm-level-up
//
//  Created by kgh on 17/12/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int T[16];
int P[16];
int n =0;
int max_num = -1;
void dfs(int sum, int idx){
    
    if(idx == n+1){
        if(sum > max_num){
            max_num = sum;
        }
        return;
    }
    if(idx > n+1){
        return;
    }
    dfs(sum+P[idx], idx+T[idx]);
    dfs(sum,idx+1);
}

int main(void){
    
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> T[i] >> P[i];
    }
    dfs(0,1);
    cout << max_num << '\n';
    return 0;
}


혹시라도 0,1에서 왜 시작하는거지? 라는 의문이 있으신분은 아래와 같이 구현하여도 상관은 없습니다. 단지 문제의 조건에 부합시키기 위해 위와 같이 작성한것 뿐입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
//  11_백준_퇴사_14501.cpp
//  algorithm-level-up
//
//  Created by kgh on 17/12/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int T[16];
int P[16];
int n =0;
int max_num = -1;
void dfs(int sum, int idx){
    
    if(idx == n){
        if(sum > max_num){
            max_num = sum;
        }
        return;
    }
    if(idx > n){
        return;
    }
    dfs(sum+P[idx], idx+T[idx]);
    dfs(sum,idx+1);
}

int main(void){
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> T[i] >> P[i];
    }
    dfs(0,0);
    cout << max_num << '\n';
    return 0;
}


Share