[ boj : 1821] 수들의 합

www.acmicpc.net/problem/1821

1821번: 수들의 합

문제 : 파스칼 삼각형의 형태로 수들이 존재합니다. 맨 윗줄은 1부터 n까지의 수들만이 주어지고 맨마지막 수를 만들수 있는 수열을 구하는 문제입니다.

 

해설 : permutation의 개념을 알고 있고, 이를 구현할 수 있으면 쉽게 풀 수 있는 문제입니다.

만약 permutation이 뭔지는 알지만 어떻게 구현하는지 모르겠다는 분들은 이번 기회에 무조건 무조건 습득하시고 외우세요....뇌속에 박아 놓으십쇼. 중요합니다.

 

#include<bits/stdc++.h>

using namespace std;

int n,m;
int per[10],visit[10],arr[10][10];

void permutation(int depth);
bool solve();

int main()
{
	cin >> n >> m;
	permutation(0);
	return 0;
}
void permutation(int depth)
{
	if (depth == n) {
		if (solve()) {
			for (int i = 0; i < n; i++)cout << per[i]<<" ";
			exit(0);
		}
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!visit[i]) {
			visit[i] = 1;
			per[depth] = i + 1;
			permutation(depth + 1);
			per[depth] = 0;
			visit[i] = 0;
		}
	}
}
bool solve()
{
	for (int i = 0; i < n; i++)arr[0][i] = per[i];
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n-i; j++)
			arr[i][j] = arr[i - 1][j] + arr[i - 1][j + 1];
	}
	if (arr[n - 1][0] == m)return true;
	return false;
}