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

문제

시간복잡도

O(n)

해결방법

dp[i][j]는 i층 j호의 인원을 나타내며 j호 까지의아래층의 사람을 모두 더한 값이다.

dp[i][j-1]는 1호 앞의 집의 인원수이며 아래층의 1호 앞까지의 합이다. 따라서 아래층의 같은 호수 합인 dp[i-1][j]을 더하여 dp[i][j]를 구한다.

 

코드

dp는 apartment배열이다.

0층은 j호에 j명이 거주하므로 직접 구하고 시작한다.

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./example.txt";
let input = fs.readFileSync(filePath).toString().split("\n");

let input_arr = [];
let tmp = [];

for (let i = 1; i <= parseInt(input[0]) * 2; i = i + 2) {
  //input 정리
  let tmp = [input[i], input[i + 1]];
  input_arr.push(tmp);
}

let apartment = []; //아파트 dp
for (let i = 0; i <= 14; i++) {
  //아파트 1층 구하기
  tmp[i] = i;
}
apartment.push(tmp);

for (let i = 1; i <= 14; i++) {
  //2층부터 아파트 구하기
  apartment.push([0]);
  for (let j = 1; j <= 14; j++) {
    apartment[i].push(apartment[i][j - 1] + apartment[i - 1][j]);
  }
}

for (let i = 0; i < parseInt(input[0]); i++) {
  console.log(apartment[parseInt(input_arr[i][0])][parseInt(input_arr[i][1])]);
}