백준) 2775 - 부녀회장이 될테야 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• 아파트에 아래와 같은 거주 조건이 있다.
• “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 
• 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 
• 단, 아파트에는 0층부터 있고 각 층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

• k층 n호에 사는 사람 = k층 (n-1)호에 사는 사람 + (k-1)층 n호에 사는 사람

4층	1	6	21	56
3층	1	5	15	35
2층	1	4	10	20
1층	1	3	6	10
0층	1	2	3	4

 

시간복잡도

• O(k * n)

알고리즘 선택

• Dynamic Programming(동적 계획법)

---

📌 코드 설계하기

1. 문제의 input을 숫자로 변환하고 구조 분해 할당으로 테스트케이스의 수 `testCase`와 각 테스트케이스에 해당하는 층 `k`, 호 `n`의 정보를 가져옵니다.
2. 0~14층, 1~14호를 가지는 2차원 배열 `dp`를 초기화 합니다.
3. 0층의 사람 수는 각 호와 동일하므로, `dp[0][n] = n`으로 초기화합니다.
4. 모든 층에 대한 `dp` 배열 값을 할당합니다.
5. 각 `testCase` 만큼 주어진 k층 n호에 사는 사람 수를 dp배열에서 찾아 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

0회차

• 2차원 배열을 만드는 법을 잊어서 찾아보고 진행하게 되었습니다.

// 15개의 바깥 배열을 만들고 안에 15개의 배열을 만들어 0으로 채운다.
const dp = Array.from(Array(15), () => Array(15).fill(0));

 

---

📌 정답 코드

//https://www.acmicpc.net/problem/2775
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const [testCase, ...input] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

// dp배열 초기화(층은 0~14층 / 호는 1~14호)
const dp = Array.from(Array(15), () => Array(15).fill(0));

// 0층 각 호에 사는 사람들
for (let j = 0; j < dp.length; j++) {
  dp[0][j] = j;
}

// 모든 층에 대한 dp 테이블
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];
  }
}

// testCase처리
for (let i = 0; i < testCase; i++) {
  //층
  const k = input[i * 2];
  //호
  const n = input[i * 2 + 1];
  console.log(dp[k][n]);
}