[JS] 백준 2775번

백준 2775번

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

const T = Number(input.shift());

solution(T);

function solution(T) {
    for (let i = 0; i < T; i++) {
        const k = +input.shift();
        const n = +input.shift();
        const house = Array.from(Array(k + 1), () => Array(n + 1).fill(0));
        for (let i = 1; i <= n; i++) {
            house[0][i] = i;
        }
        for (let i = 1; i <= k; i++) {
            for (let j = 1; j <= n; j++) {
                house[i][j] = house[i - 1][j] + house[i][j - 1];
            }
        }
        console.log(house[k][n]);
    }
}

이해하는데도 너무 오래걸렸고 정말 정말 여태 푼 문제중 가장 어려웠다.

해설을 봐도 이해가 안되서 겨우 겨우 이해하고 나서도 왜 이렇게 코드를 썼을까 하는데 또 이해가 안되고 했는데

일단 이야기 해보자면 아파트에 비어있는 집은 없다는 점. 0층의 i호에는 i명이 산다는 점.

 

a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다.

이거 이해하는데 오래걸림 멍청하게도 다른층에 i호도 i명이 산다고 생각을 해서 더욱 오래 걸렸었다.

* 표로 이해해 보자면

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

* 각층에 1호는 늘 1명이 있고 , 오른쪽 아래 숫자와 그 숫자 대각선 왼쪽 위 숫자를 더한 값이 왼쪽 위 숫자 바로 옆에 숫자 값인 규칙이 있는데 쉽게 말하자면 0층 2호 와 1층 1호 더한 값이 1층 2호가 되는것이다.

* 즉 k층 n호에 사는 사람은 = (k-1)층 n호 + k층 (n-1)호 가 되는 규칙이 있다.

* 아니 그래서 이 규칙을 알았어 근데 이걸로 문제 어떻게 푸는데? 라고 또 막혔었는데

자바스크립트에 2차원 배열을 이용을 해야 하는 문제다.

 

자바스크립트 2차원 배열에 관한 포스팅이 하나 있어서 가져와 봤다. 

https://gent.tistory.com/296

[JavaScript] 자바스크립트 2차원 배열 선언 및 사용법

 

2775번 문제에서는 이 포스팅에 4번째 방법을 이용해서 배열을 생성을 한것 같다. 

 

이 문제를 풀면서 새롭게 알게된 지식 

 

* 배열의 shift() 함수 -> shift 메서드는 0번째 위치의 요소를 제거 하고 연이은 나머지 값들의 위치를 한칸 씩 앞으로 당깁니다. 그리고 제거된 값을 반환 합니다. ( 나중에 이 글 보고도 이해 안가면 구글에 검색하기)

const array1 = [1, 2, 3];

const firstElement = array1.shift();

console.log(array1);
// expected output: Array [2, 3] 첫번째 요소를 제거한 결과 

console.log(firstElement);
// expected output: 1 다시 반환을 해준 모습

* 여태 다른사람들 정답 코드 보면서 많이 나오긴 했는데 괜히 고집 부린다고 내 식대로 풀다가

도저히 입력을 어떻게 해야할지 모르겠어서 결국 쓰긴 했는데 앞으로 새로운걸 보면 괜히 고집부려서 안쓰고

시간 낭비 하지 말고 무엇인지 구글에 검색하고 공부해서 나중에 활용하는 식으로 공부하는게 훨씬

더 나을것 같아서 앞으로 그런식으로 할 예정이다.

* const house = Array.from(Array(k + 1), () => Array(n+1).fill(0)); 이 부분이 새롭게 보게된것들이 많아서 좀

어려웠다. 

 

우선 이 코드는 각 방당 인원수를 저장할 2차원 배열을 선언해주는 코드이다.

 

* Array.from() -> 자바스크립트의 Array는 객체(함수)다.

Array.from({length: 5}, () => 0); 이런식으로 활용을 하기도 하는데 위에 코드랑은 비슷하면서 다른 느낌이다.

 

* Array.from()의 첫번째 매개변수로 {length: 원하는 길이} 객체를 넘겨준다.

* 여기서는 length 대신 Array(k+1)을 썼는데 무슨 의미냐면 배열의 크기를 지정을 해주는 것이다.

* Array(n+1).fill(0) -> 이 부분은 각각의 요소에 n+1 개 만큼 0으로 채운다는 의미이다.  

* 실제로 k가 1이고 n이 3일때 출력하는 값을 보면 [ [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ] 이렇게 출력하는 것을 알 수 있다.

* 근데 여기서 fill() 은 무엇인가 하면은 배열의 start index부터 end index 전까지(end index는 미포함) value값으로 채워주는 함수이다.

* arr.fill(value,start,end) 기본 틀은 이렇고 https://hianna.tistory.com/399 여기에 자세히 나와있다.

 

입력을 어떻게 받는지에서 시간이 더 걸렸던것 같다.