근손실 (feat. 백준, 18429번)

근손실
https://www.acmicpc.net/problem/18429

18429번: 근손실

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
using namespace std;
int N, K, arr[9], idx[9], ans;
bool check[9];
void dfs(register int n){
    if(n == N){
        register int sum = 500;
        for(register int i = 0; i < n; ++i){
            sum += arr[idx[i]] - K;
            if(sum < 500)
                return;
        }
        ++ans;
        return;
    }
    for(register int i = 0; i < N; ++i)
        if(!check[i]){
            check[i] = true;
            idx[n] = i;
            dfs(n + 1);
            check[i] = false;
        }
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    ans = 0;
    memset(check, false, sizeof(check));
    cin >> N >> K;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n];
    dfs(0);
    cout << ans;
    return 0;
}
// *&)*@*

 

반응형

 

1. 주어진 N을 1, 2, 3, ..., N 으로 볼때 N개의 조합을 구합니다. (N개 중 N개의 조합)
2. 1번에서 구해진 조합을 기준으로 N개의 운동 키트, K의 감소량으로 계산하고 500 이상을 유지하는 조합의 개수를 구해서 출력합니다.