14501 퇴사

퇴사 (14501)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 14501 퇴사
 
int N;
 
int T[17], P[17];
int maxSum;
int solve(int sum, int day){
	// 기저 사례 : 날이 N 이상이면 끝
	if(day == N + 1) return sum;
	if(day > N + 1) return 0;
	
	int on = 0, off = 0;
	
	on += solve(sum + P[day], day + T[day]);
	off += solve(sum, day + 1);
	
	return on > off ? on : off;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N;
	
	for(int i = 1; i <= N; i++){
		cin >> T[i] >> P[i];
	}
	cout << solve(0, 1) << '\n';
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

2. 단순한 방법에서 시작할 수 없을까?

 이 책에서 많은 연습문제는 "무식하게 풀 수 있을까" 라는 질문으로 풀이가 시작된다. 시·공간의 제약을 생각하지 않고 가장 단순한 알고리즘을 만들어 보는 것이다. 이는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 방지해준다. 

 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문에, 단순한 알고리즘을 구현해두고 여기에서 좀 더 효율적인 자료 구조를 사용하거나, 최적화를 하는 등의 점진적인 개선을 통해 효율적인 알고리즘을 구현해낼 수 있다.

 

풀이

1. 브루트 포스를 적용할 수 있을까?

- "선택" 즉. 해당 상담을 하느냐 하지 않느냐 로 나눈다면 시간 복잡도는 $$O(2^N)$$ 최대 2^15 이므로 1억 보다 충분히 작다. 가능

2. 위치가 바뀌면서 바뀌는 것은 무엇일까?

- 받은 금액(합) / 날 이 바뀔 것이다. 이것을 파라미터로 사용하자.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 문제를 잘 읽지 못한 것

- N+1 일 째 되는 날 퇴사를 하기 위해서, 라는 문구를 무심코 지나쳤다. 이것은 기저사례 하나를 그냥 빼먹은 것이었어서, 틀린 정답을 도출해냈었다. 논리상으로는 찾아낼 수 없었던, 문제를 잘 읽는 것만이 이 실수를 해결해줄 수 있을 것이다.

2. 기저사례를 곰곰이 생각해보지 않은 것

- N+1 일 째 되는 날이 답이라면, 다른 예외. 즉 정답이 아닌 사례는 무엇인지에 대한 기저 사례를 추가해주지 않았었다.

3. 처음에 너무 쓸때 없는 것들을 많이 추가했던 것.

- 노트에 구현해본 알고리즘 그대로 따라가는 것이다.