[BOJ 1821 // C++] 수들의 합 6

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1821번 문제인 수들의 합 6이다.
문제는 아래 링크를 확인하자.

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

1821번: 수들의 합 6

수가 N개 있을 때, 수열의 k번째로 적힌 수(0-based index)는 최종 수에 각각 N-1 choose k번 더해지게 된다.

 

따라서, N개의 수를 사전순으로 나열해보면서(순열을 생성해보면서) 각 경우에 나오는 최종 수를 구해보는 것으로 문제를 해결할 수 있다. 이 때, 위의 관찰을 이용하면 이를 더욱 빠르게 진행할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> vec;

int N, F;
int comb[11][11];
bool visited[11];

int psum = 0;

bool func(int ith) {
	if (ith == N) {
		if (psum == F) {
			for (auto& x : vec) cout << x << ' ';
			return 1;
		}
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				visited[i] = 1;
				vec.emplace_back(i);
				psum += i * comb[N - 1][ith];
				if (func(ith + 1)) return 1;
				psum -= i * comb[N - 1][ith];
				vec.pop_back();
				visited[i] = 0;
			}
		}
	}

	return 0;
}

void combinit() {
	for (int n = 0; n < 11; n++) {
		comb[n][0] = 1;
		for (int i = 1; i < n; i++) comb[n][i] = comb[n - 1][i - 1] + comb[n - 1][i];
		comb[n][n] = 1;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	combinit();

	cin >> N >> F;
	func(0);
}