[삼성코테기출문제] 퇴사

퇴사

문제

19년 상반기 준비할 때 Brute Force부분을 공부할 때 풀었던 문제이다. 그때는 재귀함수도 확실히 몰라서(지금도 어렵지만..) 난항을 겪다가 풀었던 문제였던걸로 기억한다. 지금와서 보면 조금은 쉽게 느껴지지만 조건들이 조금 헷갈릴수도 있기 때문에 문제를 잘 읽고 파악해야 한다.

문제 풀이

퇴사 문제를 다시 풀면서 재귀함수에 대해서 좀 감이 오기 시작한거 같다. 현재 함수에서 처리해야할 조건이 무엇인지 재귀로 넘어가는 다음 함수의 조건은 무엇인지를 잘 파악해야하는 것 같다.

입출력 조건

풀이 과정
먼저 재귀함수의 return조건을 생각해보자. T[i]와 P[i]가 N개 있다면 인덱스는 N-1까지이다. 그러므로 하나의 일이 a일에 끝나야만 a+1일 부터 다음 일을 할 수 있다.

만약 N일 이전에 끝마친 일들이 최대값일 때는 그 이후로는 1일씩 증가시켜 day=N이 될 때 최대값 비교하여 처리한다. 그 뒤로 한 일들을 끝마칠 수 있는 날짜가 N을 넘는다면 할 수 없는 일이므로 종료시켜준다.

만약 N일에 맞춰서 끝날때 최대값일 때는 위와 같이 day=N일 떄 최대값 처리를 해주면 된다.

#include<iostream>

using namespace std;
const int MAX = 15;

int N, Max;
int P[MAX], T[MAX];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> T[i] >> P[i];
	}
}
//T[i] : 3  5  1  1  2  4  2
//P[i] : 10 20 10 20 15 40 200

void Process(int sum, int day) {
	if (day == N) {
		if (Max < sum)Max = sum;
		return;
	}
	else if (day > N)return;	
	Process(sum + P[day], day + T[day]);
	Process(sum, day + 1);
}
void Solution() {
	Input();
	Process(0, 0);
	cout << Max << endl;
}
int main() {
	freopen("07.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	Solution();
	return 0;
}