[BOJ][백트래킹][실4]][14501] 퇴사

문제 링크

문제 링크

풀이

알고리즘

N자리 K진수를 적용해서 해결하는 문제입니다. 선택한다/안한다의 방법을 적용합니다.

[이론][완전탐색][N자리 K진수] Chapter 2를 확인해보세요.

정답 코드

#include <bits/stdc++.h>

#define MAX 20
using namespace std;
typedef long long ll;

int n = 0, k = 0; //N:배열의 길이 , K: 진수
int input[MAX][2];
int v[MAX];
bool visited[MAX];
int ans = 0;

// depth : depth째 날의 일을 할지 말지 결정한다.
void recur(int depth, int score) {
  if (depth > n) return;


  // 일을 할 수 있으면 한다.
  // 하루가 걸리는 일도 할 수 있도록 범위를 설정한다.
  if (depth + input[depth][0] - 1 <= n) {
    ans = max(ans, score + input[depth][1]);
    recur(depth + input[depth][0], score + input[depth][1]);
  }
  // 일을 안한다. 못하는 경우도 안하는 경우에 포함된다.
  recur(depth + 1, score);
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> input[i][0] >> input[i][1];
  }
  recur(1,0);
  cout << ans << "\n";
  return 0;
}

Success Notice: N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.