[백준🔉][14501] 퇴사 문제 해설
👓 문제 요약
우리팀에서 가장 열심히, 돈을 위해 직장을 다니던 훌륭한 백준 직원이 퇴사를 하려고 한다. 퇴사하기 전까지 가장 많은 돈을 버는 (가장 많은 일을 하는게 아닌) 계획을 짜고 수행하려 한다. 백준이가 돈을 많이 벌 수 있게 도와주자.
자세한 문제 설명과 제한 사항은 백준 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
우리 백준이는 N + 1 일에 퇴사하기 때문에 N 일 까지는 일을 한다. 상담완료에 걸리는 일자가 3일이면 해당하는 날을 포함해 3일 이라는 것을 명심하자.
전형적인 DFS 문제이며 시작하는 일부터 N 일까지 탐색 후, 얼마를 벌었는지 가능한 케이스를 모두 조사하는 것이다.
🥽 소스코드 및 소스해석
백준 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 코드에는 테스트 코드가 존재합니다.
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
struct Task {
int period;
int earn;
};
using namespace std;
void dfs(int idx, int endDay, int money);
vector<Task> myTask;
int myMoney = -1;
int main() {
int TC;
cin >> TC;
myTask.assign(TC, {0, 0});
for (int i = 0; i < TC; i++)
cin >> myTask[i].period >> myTask[i].earn;
for (int i = 0; i < myTask.size(); i++)
if (myTask[i].period + i <= myTask.size())
dfs(i + 1, i + myTask[i].period, myTask[i].earn);
cout << myMoney;
}
//
void dfs(int idx,int endDay,int money) {
for (int i = idx; i < myTask.size(); i++)
if(endDay <= i && myTask[i].period + i <= myTask.size())
dfs(i + 1, i + myTask[i].period, money + myTask[i].earn);
myMoney = max(myMoney, money);
}🔨 문제 후기
DFS의 전형적인 문제로서 기본이 되는 문제였다. 나는 문제를 잘못 읽어서 1시간동안 이상한 짓을 했다.
퇴사를 하기 전까지 열심히 일하는 백준이. 백준이 상사는 훌륭한 부하가 나가기 때문에 매우 심기가 불편할 것 같다.
Series
Algorithms
이 글은 "Algorithms" 시리즈의 12번째 기록입니다.
- 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
- 02[프로그래머스][2019 kakao] 블록게임 해설
- 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
- 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
- 05[프로그래머스][2019 kakao] 후보키 문제 해설
- 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
- 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
- 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
- 09[백준🔉][16234] 인구이동 문제 해설
- 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
- 11[프로그래머스✈][2020 kakao] 동굴 탐험
- 12[백준🔉][14501] 퇴사 문제 해설
- 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
- 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
- 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
- 16[leetcode][15] 3sum 문제풀기!
- 17[leetcode][16] 3sum closet 문제풀기!
- 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
- 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
- 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
- 21[leetcode][31] Next Permutation 문제풀기!
- 22[leetcode][32] Longest Valid Parentheses 문제풀기
- 23[leetcode][40] Combination Sum II 문제풀기!
- 24[leetcode][42] Trapping Rain Water 문제풀기!
- 25[leetcode][43] Multiply Strings 문제풀기!
- 26[leetcode][44] Wildcard Matching 문제풀기!
- 27[leetcode][45] Jump Game II 문제풀기!