IF - 수열 추측하기

문제

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

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

예시

N	F	result
4	16	[3,1,2,4]

풀이

• 수열과 조합, 이항계수를 이용하여 푸는 문제이다.
• 주어진 문제에서 3 1 2 4 밑의 4 3 6 은 각각 3+1 , 1+2, 2+4 로 풀어낼 수 있다. 또 4 3 6 밑의 7 9 역시 각각 3+1+1+2, 1+2+2+4 로 풀어낼 수 있다.
• 이렇게 최종 숫자인 16까지 내려오면, 16 === 3+1+1+2+1+2+2+4로 나타낼 수 있으며, 식의 뒷변을 축약하면 (1*3) + (2*3) + (3*1) + (4*1) 로 표현된다.
• 다시 삼각형의 맨 위로 올라가서, 3 1 2 4 와 방금 축약한 식을 비교해보면

[3,1,2,4]
[1,3,3,1]

• 위와 같이 매핑된다는 것을 알 수 있다.
• 1 3 3 1 은 주어진 숫자가 n개라고 했을 때, 각각 nC0 nC1 nC2 nC3 과 같다.
• 즉, 위의 테이블에서 위 배열은 1~N 까지의 수열의 경우의 수 중 하나이고, 밑 배열의 원소들은 각각 n-1C0, n-1C1, n-1C2, n-1C3 이다.
• 이를 활용해 DFS 로 답을 구하면 아래와 같다.
• 한참 고민하다가 풀이를 보고 나서 혼자 다시 풀어본 문제인데, 풀이를 안봤더라면 못풀었을 것 같다..

코드

const solution = (n, f) => {
	const answer = [];
	const temp = [];
	const check = new Array(n).fill(0);
	const combiArr = [];
	const permuArr = [];
	let flag = 0;
	const memo = Array.from(Array(11), () => Array(11).fill(0));
	const combi = (n, r) => {
		if (memo[n][r]) return memo[n][r];
		if (n === r || r === 0) return 1;
		else {
			return (memo[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
		}
	};

	const DFS = (L, sum) => {
		if (flag) return;
		if (L === n && sum === f) {
			answer = [...permuArr];
			flag = 1;
		} else {
			for (let i = 0; i < n; i++) {
				if (check[i] === 0) {
					check[i] = 1;
					permuArr[L] = i + 1;
					DFS(L + 1, sum + permuArr[L] * combiArr[L]);
					check[i] = 0;
				}
			}
		}
	};

	for (let i = 0; i < n; i++) combiArr[i] = combi(n - 1, i);

	DFS(0, 0);
	return answer;
};