백준 2775번: 부녀회장이 될테야(I'll be the president of the women's association) Node.js(JavaScript)

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

Code

최종 제출 코드

😢 이런 저런 패턴이 많이 보여서, 어떤 패턴으로 접근할 지 고민을 많이 했다.

😊 문제의 의도는 a-1층의 1호부터 b호까지 모두 더하라는 것이 아닐 것이다. 물론 더해도 된다. 하지만 시간이 오래 걸린다.

1	6	21	56	126
1	5	15	35	70
1	4	10	20	35
1	3	6	10	15
1	2	3	4	5

예를 들기 위해, 4층, 1-5호까지 있는 아파트를 표로 작성해봤다(참고로 층은 0부터 시작한다)
어떤 패턴이 있는지 잘 살펴보면, [a행, b열]에 있는 값은 [a행, b-1열] + [a-1행, b열]의 값으로 이루어져 있다.

또한, 가장 아래 행의 각 열은 1부터 b까지 1씩 순차적으로 증가하는 값을 가지며, 왼쪽의 첫 번째 열은 항상 1 값만 갖는다.

입력으로 a=2, b=3을 받았다고 가정해보자
[2, 2] == 4, [1, 3] == 6이라는 것을 알 수 있고, 이 값을 더하면 4+6=10. 곧, [2, 3]의 값이다.
이 패턴을 가지고 코드를 작성해보면 위의 코드가 나온다.

외부 for loop에서 배열을 항상 [1]부터 시작하도록 초기화해준다.
내부 for loop에서는 가장 아래 행이면 1씩 증가하도록 if 조건문을 걸어주고,
그 외 경우는 위의 [a행, b-1열] + [a-1행, b열] 패턴에 맞도록 값을 저장해준다.
그리고 마지막에 알고 싶은 층과 호수를 배열의 인덱스에 넣고 찾아주면 된다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

// I'll be the president of the women's association

// 2nd Solution - Good

// For submit

// const fs = require('fs');

// const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(num => Number(num));

// For local test

const input = [2, 1, 3, 2, 3];

const T = input.shift();

for (let i = 0; i < T; i++) {

const a = input.shift();

const b = input.shift();

const apartment = [];

for (let i = 0; i <= a; i++) {

apartment.push([1]);

for (let j = 1; j < b; j++) {

if (i === 0) {

apartment[i].push(j + 1);

} else {

apartment[i].push(apartment[i][j - 1] + apartment[i - 1][j]);

}

}

}

const floor = a;

const room = b - 1;

console.log(apartment[floor][room]);

}