백준 14501번 퇴사 (삼성 SW 역량테스트 기출문제)

사용한 알고리즘: 브루스 포스, DP


삼성 SW 역량테스트 기출문제 중 제가 정말 예전에 풀었던 문제가 있어서 코드만 올려보겠습니다.

모든 지점을 다 보면서 dp 형식으로 저장해 나갔네요...

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N, A[20], B[20], dp[20];
	int main(){
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
	scanf("%d %d", &A[i], &B[i]);
	for (int i = 1; i <= N; ++i){
	if(i+A[i]-1>N)
	B[i] = 0;
	for (int j = 1; j <= N; ++j){
	if(j+A[j]-1<=i)
	dp[i] = max(dp[i], B[j] + dp[j-1]);
	}
	}
	printf("%d\n", dp[N]);
	return 0;
	}

view raw BOJ 14501.cpp hosted with ❤ by GitHub