가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. (단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.)
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
4 16
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.
3 1 2 4
파스칼의 삼각형은 이렇게 순열에 대해 각 순열의 값을 더해가며 최종적으로 가장 밑의 수는 1+2+2+2+3+3+3+4의 형태가 된다.
하지만 1~n까지 순열의 경우의 수는 n! 이다. 만약 n이 커지면 커질 수록 시간 복잡도가 증가하여 연산에 오랜 시간이 걸릴 것이다.
모든 순열을 파스칼의 삼각형에 대입하는 것이 아닌 이항 정리를 고려해 볼 수도 있다. 결국 16이라는 숫자는 1를 1번, 2와 3을 3번, 4를 1번 곱한 후 더한 값이기 때문이다.
즉, 파스칼 삼각형의 가장 위 층의 숫자들을 각각 이항 정리의 자릿수와 곱한 후 더하면(1 x 3 + 3 x 1 + 3 x 2 + 1 x 4) 파스칼 삼각형의 가장 밑의 수와 동일한 결과 값을 얻어 낼 수 있다.
전체적인 알고리즘의 흐름은 다음과 같다.
- n에 대한 이항 계수를 구한다.
- 순열을 만들어가며 (순열의 각 자리수 * 조합 수의 각 자리수) 들을 각각 더한 후 파스칼 삼각형의 최종 값과 비교한다.
- 만약 같다면 그 순열을 반환한다.
- 아니라면 다른 순열을 만든 후 2의 과정을 반복하여 3을 도출해낸다.
function solution(n, f) {
// answer와 flag(순열이 answer에 들어갈 경우 종료 하기 위함)
let answer,
flag = 0;
// 조합 수에 대해 메모이제이션 하기 위한 dy
let dy = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
// 순열 생성을 위한 check 배열
let ch = Array.from({ length: n + 1 }, () => 0);
// 순열 p
let p = Array.from({ length: n }, () => 0);
// 조합 수 b
let b = Array.from({ length: n }, () => 0);
// combination 함수를 통해 조합수를 도출
function combination(n, r) {
if (dy[n][r] > 0) return dy[n][r];
if (n === r || r === 0) return 1;
else return (dy[n][r] = combination(n - 1, r - 1) + combination(n - 1, r));
}
// answer를 도출해내기 위한 DFS 함수
function DFS(l, sum) {
// 만약 flag === 1이면 순열이 answer에 들어갔기 때문에 종료
if (flag) return;
// 만약 순열이 만들어졌고 순열의 각 자리수 * 조합 수의 각 자리수를
// 각각 더한 값이 f(가장 밑의 줄의 수)와 같다면 answer에 추가 후 flag = 1
if (l === n && sum === f) {
answer = p.slice();
flag = 1;
// 순열을 생성해가며 기존 sum에서 순열의 각 자리수와 조합 수의 각 자리수를 곱해서 더함
} else {
for (let i = 1; i <= n; i++) {
if (ch[i] === 0) {
ch[i] = 1;
p[l] = i;
DFS(l + 1, sum + p[l] * b[l]);
ch[i] = 0;
}
}
}
}
// 조합 수를 b에 추가
for (let i = 0; i < n; i++) {
b[i] = combination(n - 1, i);
}
DFS(0, 0);
return answer;
}
console.log(solution(4, 16));