[백준/CPP] 근손실 - 18429번 / CPP 풀이

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

18429번: 근손실

 

백준 백트래킹의 대표적인 문제인 "N과 M"이랑 비슷한 문제이다.

 

문제를 요약하자면 N일 동안 매일 다른 키트를 사용하여 운동하는데 하루에 근육이 K만큼 빠진다고 한다.

매일 매일 다른 키트를 사용하여 N일 동안 3대 500을 유지하는 문제이다.

단 하루라도 500 이하로 떨어지면 안되므로 Ni - K > 500 인 순열을 찾는 문제이다.

 

For 문을 0 ~ N까지 돌리면서 만약 그 날 500 이하로 떨어지면 그 순열은 탈락시키고 N일까지 도달한 순열의 갯수만 카운트해준다.

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int ans;
int n, k;

vector <int> vc;
bool visited[8];

void dfs(int cnt, int total) {
	// 3. 만약 넘어온 total 값이 500보다 작으면 해당 순열은 정답에서 제외된다.
	if (total < 500)
		return;

	// 4. N일 간의 운동 루틴 동안 근육량이 500 밑으로 떨어지지 않았다면 성공!
	if (cnt == vc.size()) {
		ans++;
		return;
	}

	for (int i = 0; i < vc.size(); i++) {
    	// 1. 해당 루틴에서 사용하지 않은 키트만을 선별하기 위한 방문 체크 배열
		if (!visited[i]) {
			visited[i] = true;
            // 2. 현재 total + 그 날 사용하는 키트 - 근손실량을 넘겨준다.
			dfs(cnt + 1, total + vc[i] - k);
			visited[i] = false;
		}
	}
}

int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int c; cin >> c;
		vc.push_back(c);
	}

	dfs(0, 500);

	cout << ans;
}