백준[18429] 근손실

문제 설명

문제 링크

http://icpc.me/18429

풀이

3대 500을 찍고 싶은 헬창이라면 누구나 풀어봐야 할 루틴을 정하는 문제이다.

백트레킹으로 모든 경우를 확인하며 풀 수 있다.

코드

#include <cstdio>
#include <vector>

using namespace std;

vector<int> v;
int n, k, ans;
bool visited[10];

void solve(int cur, int sum) {
    if (sum < 0) return;
    if (cur == n) {
        ans++;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        solve(cur + 1, sum + v[i] - k);
        visited[i] = false;
    }
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        int tmp; scanf("%d", &tmp);
        v.push_back(tmp);
    }
    solve(0, 0);
    printf("%d", ans);
}