[PS][완전탐색][N자리 K진수]/[BOJ][14501][퇴사]

boj14501.cpp

#include <iostream>

using namespace std;

int n=0;
int input[20][2];
int ans = 0;
/*
depth : depth날짜의 일을 할지 말지 결정해야 한다. = depth-1일까지는 일을 완료한 상태이다.
score : depth-1일까지 완료한 상태까지 번 돈
*/

void recur(int depth, int score){
  if(depth>=n){
    ans = ans < score ? score : ans;
    return;
  }
  if(depth + input[depth][0] -1 <n){ //depth날짜의 일을 진행할 때 마지막날이 출근하는 날이면 가능
    recur(depth+input[depth][0], score + input[depth][1]);
  }
  recur(depth+1, score);
}
int main(void){
  cin.tie(NULL);
  ios::sync_with_stdio("false");
  cin>> n;
  for(int i=0; i<n; i++){
    cin>> input[i][0] >> input[i][1];
  }

  recur(0,0);
  cout << ans <<"\n";
  return 0;
}

//일단 일을 하고, 딱 N일 차에 일이 끝나는 경우에만 답을 갱신하는 코드

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int arr[25][2];
int ans = 0;
/*
depth : 일끝나고 depth일이 되었다. == depth 번째일을 시작할지말지 결정해야한다.
*/

void recur(int depth, int money) {
	//n+1번째에 시작해야하는 일은 할 수 없다.
	if (depth == n) {
		ans = ans < money ? money : ans;
		return;
	}
	if (depth > n) return;
	//depth 번쨰의 일을 한다.
	recur(depth + arr[depth][0], money + arr[depth][1]);
	//depth 번째의 일을 하지 않는다.
	recur(depth + 1, money);
}
int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	recur(0, 0);
	cout << ans << "\n";
	return 0;
}

//int형 return을 가지는 코드

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int dp[1000001];
int input[1000001][2];

//n = 4
//0	1	2	3  4(퇴사)
//1	1	1	1  x
//1	2	3	4  x


int recur(int curr) {
	//return [curr,마지막날]의 일을 해서 얻을 수 있는 최대 돈
	int ret = 0;
	if (curr == n) return 0;
	//input[curr]의 일을 못하는 경우
	if (curr + input[curr][0] > n) return recur(curr + 1);
	//input[curr]의 일을 할 수 있는 경우
	return max(recur(curr+input[curr][0]) + input[curr][1],recur(curr+1));
}



int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input[i][0] >> input[i][1];
	}

	cout << recur(0);

	return 0;
}