[2775] 부녀회장이 될테야 - JavaScript

로직은 잘 짰다고 생각했는데 생각지도 못한 곳에서 실수를 해서 시간을 많이 쓴 문제다.

/* 문제 */
평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

처음에는 재귀 함수로 풀려다가 RangeError: Maximum call stack size exceeded 가 떠서 직접 풀기로 결정.

원하는 층의 사람 수를 구하려면 아래층의 사람 수가 필요하기 때문에 2차원 배열로 해결했다.

 

k층 n호에 살고 있는 사람 수를 구하려면 k-1층의 1호부터 n호까지의 사람 수를 더해야 한다. 이 때 k층의 n-1호에는 k-1층의 1호부터 n-1호까지의 사람 수를 더한 수가 살고 있다. 따라서 (k층 n-1호의 사람 수) + (k-1층 n호의 사람 수)를 하면 k층 n호의 사람 수를 구할 수 있다. 각 케이스 별로 필요한 만큼의 값(k층 n호까지의 사람 수)만 계산하여 배열에 저장했다.

 

// 틀린 코드

const fs = require("fs");
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
console.log(input);
const t = parseInt(input[0]);
for (let i = 1; i < t + 2; i += 2) {
  const k = parseInt(input[i]);
  const n = parseInt(input[i + 1]);
  let p = new Array(n).fill(0).map(() => new Array(k).fill(0));
  console.log(p);
  for (let j = 0; j < n; j++) {
    p[0][j] = j + 1;
  }
  for (let kk = 1; kk < k + 1; kk++) {
    for (let nn = 0; nn < n; nn++) {
      if (nn === 0) {
        p[kk][nn] = 1;
      } else {
        p[kk][nn] = p[kk - 1][nn] + p[kk][nn - 1];
      }
    }
  }
  console.log(p[k][n - 1]);
}

위 코드에는 두 가지 문제점이 있었다.

    1. 배열 크기(층 수 k) 잘못 설정

처음 코드를 제출했을 때 런타임 에러 (TypeError)가 떠서 당황했다. 내가 입력해 본 테스트 케이스에서는 모두 정답이 나왔기 때문이었는데, 몇 번 테스트를 해보니 n=1일 때 에러가 발생했다. 이유는 내 로직 상 (k+1)*n 배열을 선언했어야 하는데 n*k 배열을 선언해 존재하지 않는 인덱스에 접근했기 때문..

// k=5, n=1이라고 했을 때
// 내가 선언해야 하는 배열 형태
[[0], [0], [0], [0], [0], [0]]
// 내가 선언한 배열 형태
[[0, 0, 0, 0, 0]]

n이 2 이상일 때는 요소가 두 개 이상인 이차원 배열이 만들어지긴 했기 때문에 어찌저찌 에러는 발생하지 않았던 것 같다.

심지어 처음에는 n*k 배열을 k*n 배열로 수정해서 한참을 또 삽질했다.

 

    2. 전체 input 케이스 수 잘못 설정

1번을 수정한 후에는 답이 틀렸다고 떴다. 이유는 전체 로직을 반복하는 반복문의 범위를 t + 1까지로 설정했기 때문이었다. i를 2씩 증가시켰으니 2를 더하면 된다고 단순하게 생각했었는데 각 케이스마다 input 배열의 요소를 두 개씩 사용하기 때문에 t * 2를 해줬어야 하는 것이다.

 

// 최종 코드(정답 코드)

const fs = require("fs");
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
const t = parseInt(input[0]);
for (let i = 1; i < t * 2; i += 2) {
  const k = parseInt(input[i]);
  const n = parseInt(input[i + 1]);
  let p = new Array(k + 1).fill(0).map(() => new Array(n).fill(0)); //(k+1)*n 이차원 배열
  for (let j = 0; j < n; j++) {
    p[0][j] = j + 1;
  }
  for (let kk = 1; kk < k + 1; kk++) {
    for (let nn = 0; nn < n; nn++) {
      if (nn === 0) {
        p[kk][nn] = 1;
      } else {
        p[kk][nn] = p[kk - 1][nn] + p[kk][nn - 1];
      }
    }
  }
  console.log(p[k][n - 1]);
}