14501 퇴사

https://www.acmicpc.net/problem/14501

실버 3

14501번: 퇴사

 

 

DP 문제, 브루트포스

최대 15임으로 2^15 의 경우로 부분집합을 모두 구할 수 있음.

하지만, 시간초과로 인해 caching 을 사용 (memset > (from cstring)) // initialized to -1

 

DP 식

solve[i] = MAX(solve(i+T[i])+P[i], solve(i+1));

: i 일에 얻을 수 있는 최대 포인트, 

- solve(i+T[i])+P[i] : i 번째 일을 선택할 경우 T[i]동안 다른 업무 불가함으로 solve(i+T[i]) & P[i]는 i번쨰 업무를 선택함으로써 얻을 수 있는 포인트

- solve(i+1) : i 번째 일을 선택하지 않을 경우 그날을 스킵한 것이기 때문.

 

caching

down-top 문제

1 부터 N 까지 서칭함

구한 solve(i) 의 결과를 cache 로 저장을 한다.

디폴트는 -1 로 세팅을 하는데

memset(cache, -1, sizeof(cache));

로 한줄 세팅한다.

cache 에 저장된 값이  디폴트값인 -1 가 아닐경우 매번 계산하지 않고 cache 에 저장된 리턴해주어 사용한다.

Therefore, 각 days 에 대한 계산은 한번씩만 이루어진다.

 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 20;
int T[MAXN], P[MAXN];
int N;
int cache[MAXN]; // values initialized to -1


int solve(int i) {

	if(i > N)
		return 0;

	int &ret = cache[i]; //return value
	if (ret != -1) return ret;

	if(i + T[i] <= N+1)
		ret = solve(i+T[i])+P[i];

	return ret = max(ret, solve(i+1));
}


int main(int argc, char **argv) {
	scanf("%d", &N);

	for(int i=1; i<=N; i++)
		scanf("%d %d", &T[i], &P[i]);

	memset(cache, -1, sizeof(cache));

	int answer = solve(1);

	printf("%d\n",answer);
	return answer;


}

 

참고)

https://www.youtube.com/watch?v=0yTB4nqk8ys