[BEAKJOON / node.js] 2775 부녀회장이 될테야

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

---

// test.txt
2
1
3
2
3

sol1

const [cases,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');

for (let i = 0; i < cases; i++) {
  const k = +input.shift();
  const n = +input.shift();
  const arr = Array.from({length : k+1}, () => Array(n + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    arr[0][i] = i;
  }
  for (let i = 1; i <= k; i++) {
    for (let j = 1; j <= n; j++) {
      arr[i][j] = arr[i - 1][j] + arr[i][j-1];
    }
  }
  console.log(arr[k][n]);
}

// 6
// 10

0으로 초기화된 이차원 배열을 만들고 문제에서 주어준 규칙을 하나씩 해결하며 케이스 수만큼 반복한다.

 

1.

for (let i = 0; i < cases; i++) {
  const k = +input.shift();
  const n = +input.shift();
  const arr = Array.from({length : k+1}, () => Array(n + 1).fill(0));
 }

shift 메서드는 원본 배열을 변경시킨다. for문이 돌 때마다 케이스에 해당하는 k, n을 빼서 사용한다. 새로운 케이스가 시작할 때마다 0으로 초기화된 배열을 사용해야 하므로 이차원 배열도 for문 내부에서 만들어준다.

 

2.

  for (let i = 1; i <= n; i++) {
    arr[0][i] = i;
  }

문제에서 <단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.> 고 제시한 조건을 먼저 해결한다.

 

3.

case 1
//  [ 0, 1, 3, 6 ] 
//  [ 0, 1, 2, 3 ]

case 2
//  [ 0, 1, 4, 10 ]
//  [ 0, 1, 3, 6 ]
//  [ 0, 1, 2, 3 ]

이 문제의 규칙을 이해 하려면 먼저 주어진 예시로 이차원 배열을 만들어 보면 되는데, 문제에서 반복적으로 나오는 규칙은 선택된 방의 왼쪽과 아래쪽의 합인걸 알 수 있다.

  for (let i = 1; i <= k; i++) {
    for (let j = 1; j <= n; j++) {
      arr[i][j] = arr[i - 1][j] + arr[i][j-1];
    }
  }
  console.log(arr[k][n]);

따라서 이차원 배열을 돌기위한 이중 for문을 만들고 각방의 인원이 왼쪽 요소, 아래쪽 요소의 합이 되도록 배열은 만들어 준다. 배열이 제대로 만들어졌는지 콘솔 해보고 맞는 출력을 해주면 된다.

 

sol2

const input = require('fs').readFileSync('test.txt').toString().trim().split('\n').map(Number);
function solution(input) {
  let testCase = input[0];
  
  for(let i = 0; i < testCase; i++) {
      let current = 2 * i + 1;
      let k = input[current];
      let n = input[current + 1];

      let result = 1;
      for(let j = 0; j < n - 1; j++) {
          result = result * (k + n - j);
      }
      
      for(let j = 1; j < n; j++) {
          result = result / j;
      }
      
      console.log(Math.abs(result));
  }
}
solution(input);
//6
//10

다른 풀이에 대해 서칭하다 발견한 방법인데, 배열의 모양이 파스칼의 삼각형을 이루며 이항계수를 이용한 풀이라고 한다. 빈 배열을 만들지 않고 풀 수 있는 방법 중 가장 괜찮아 보였는데 원리를 아직 이해하지 못했다. 문과

언젠가 수학적 지식이 늘게되면 돌아와 이해해보기로..