[JS] 백준 2775: 부녀 회장이 될테야

문제 요약

백준 2775번: 부녀회장이 될테야

• k와 n에 대해 k층에 n호에는 몇명이 사는지 출력
• 첫 번째 줄에 Test case의 수 T가 주어진다
• 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
• 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.
• a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다

입력

2 
1 
3 
2 
3 

출력

6
10

문제 분석

• 입력값을 살펴보면 아래와 같이 표현할 수 있다. 이를 분리하고 어떻게 관리할건지 고민해보자.

2 // T의 수
1 // k,층
3 // n,호
2 // k,층
3 // n,호

• 배열의 초기화를 신경써야한다. 각 층에 대한 generate를 먼저 진행해야 입력값이 바뀌었을 때도 undefined 문제가 일어나지 않는다.

문제 설계

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const [i, ...arr] = input;

const dp = Array.from(Array(15), () => Array(15).fill(0));
for (let i = 0; i < dp.length; i++) {
  dp[0][i] = i;
}

for (let i = 1; i < dp.length; i++) {
  for (let j = 1; j < dp.length; j++) {
    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
  }
}

for (let t = 0; t < i; t++) {
  const k = arr[t * 2]; // 층
  const n = arr[t * 2 + 1]; // 호

  console.log(dp[k][n]);
}

2차원 배열 생성 및 0층 초기화하기 Array.from fill

• 0층의 i호에는 i명이 산다고했으니 1,2,3,4,5...순으로 채워준다.
• 배열의 length가 15인 이유는 인덱스는 0부터 시작하므로 14층, 14호까지 만들기 위해서는 필요하다.
• 층은 0부터시작하고 호는 1부터 시작하지만 호를 위해 또 0자리를 뺀 배열을 생성하는건 비효율적일 것 같아 0으로 초기화해주는걸로 구분했다.

const dp = Array.from(Array(15), () => Array(15).fill(0));
for (let i = 0; i < dp.length; i++) {
  dp[0][i] = i;
}

점화식 세우기 for문

• a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다 라는 규칙을 적용한 점화식을 세운다
• 아래층의 1호부터 b호, 즉 지금 살려고하는 호수까지의 사람들을 합해야한다.
• 그 말을 좀 더 쉽게 바꿔본다면 만약 내가 2층의 2호에 살고싶다면 내 왼쪽(아랫층의 ~1층까지의 누적 합) 그리고 내가 살 호의 아랫층의 수를 더하는 점화식을 세우면 간단하다.

for (let i = 1; i < dp.length; i++) {
  for (let j = 1; j < dp.length; j++) {
    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
  }
}

해당 테스트 케이스의 층 호를 출력 for 문

• i는 입력 횟수이다.
• 인풋 값이 입력값,층,호,층,호(입력값만큼)이다.
• 그러므로 층은 짝수, 호는 홀수 인덱스에 있다.

for (let t = 0; t < i; t++) {
  const k = arr[t * 2]; // 층
  const n = arr[t * 2 + 1]; // 호

  console.log(dp[k][n]);
}

결론

규칙은 쉽게 찾았는데, 배열의 초기화를 제대로하지못해 배열을 못 찾는 이슈로 많이 틀렸다... 설계와 흐름이 어색하지않게끔 자꾸 연습해야겠다.