본문으로 건너뛰기
poylog

개발·AI

2775 부녀회장이 될테야

1분

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

백준 2775번 부녀회장이 될테야 문제 설명과 아파트 거주 규칙
javascript
// test.txt
2
1
3
2
3

sol1

javascript
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.

javascript
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.

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

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

3.

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

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

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

javascript
  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

javascript
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

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

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