[백준 1821] 수들의 합 6 (C++)

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

문제

---

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

3 1 2 4
 4 3 6
  7 9
   16

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

입력

---

첫째 줄에 두개의 정수 N(1 ≤ N ≤ 10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하인 자연수이다.

 

출력

---

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

 

문제 풀이

---

브루트 포스 문제.

 

N이 최대 10까지이므로 백트래킹 형식의 브루트포스로 접근하면 풀 수 있다. 첫번째 줄 수의 순서를 브루트포스로 정한 후, 함수의 depth가 N까지 깊어지면 N번째 줄까지 계산하여 F와 일치하는지 확인한다. 첫번째 줄의 수의 순서를 정할 때 1부터 N까지 탐색하여 해당 수가 쓰였는지 확인하고 쓰이지 않았다면 현재 depth에 해당하는 인덱스의 값은 해당 수가 된다. 따라서 사전 순으로 탐색하게 되므로, F와 일치하는 첫번째 것이 답이 된다.

 

아래는 코드.

#include <iostream>
using namespace std;
int N, F;
int** arr;
bool* isUsed;
bool isFound;

void dfs(int depth)
{
	if (depth == N)
	{
		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] == F)
		{
			for (int i = 0; i < N; i++)
			{
				cout << arr[0][i] << " ";
			}
			isFound = true;
		}
	}
	else
	{
		for (int i = 1; (i <= N && isFound == false); i++)
		{
			if (isUsed[i] == false)
			{
				arr[0][depth] = i;
				isUsed[i] = true;
				dfs(depth + 1);
				isUsed[i] = false;
			}
		}
	}
}

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

	isFound = false;
	cin >> N >> F;
	arr = new int* [N];
	isUsed = new bool[N+1];
	for (int i = 0; i < N+1; i++)
	{
		isUsed[i] = false;
	}
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
	}
	dfs(0);
	return 0;
}