[백준 Node.js/Javascript] 2775번 부녀회장이 될테야!

코드

해당 코드는에서  여기 블로그를 참고하여 적은 것이다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString()split('\n').map(el => +el);
    
let T = input.shift();

for (let i = 0; i < T; i++) {
    let k = input.shift() // 두번째 케이스가 들어오기 위해 원본배열에서 제거해준다
    let n = input.shift() // 어차피 첫번째 값이 제거되면 그 다음에 있는 요소가 첫번째가 된다.
    let residents = [];

    // 각 룸의 인원수를 만드는 배열 작업 (층별로 배열을 만듦, 층이 곧 인덱스)
    for ( let i = 0; i <= T; i++ ) {
        residents.push([1]); // 각 층의 1호는 무조건 1
        for( let j = 1; j <= n; j++ ) {
            if( i == 0 ) {
                residents[i].push(j+1); // 2호부터는 1씩 증가하니까 j+1 해주기
            }
            else { //1층 이상부터 적용되는 공식
                residents[i].push((residents[i][j-1]) + residents[i-1][j])
            } //1층일 때 
        }
    }                
    
    const floor = k;
    const room = n-1;
    console.log(residents[floor][room]);
}

 

조건

a층 b호에 사는 사람의 수는 아래층 1호부터 b호까지 사람들의 수의 합이다.

 

제한

총 층수: 13층 (0층부터 시작)

총 호수: 14호 (1호부터 시작)

 

질문

k층 n호에 살고있는 사람의 수는?

 

풀이

1. (k-1)층 n호까지 사는 사람의 수를 구한다.

 

 

2. 그렇다면 그 수를 어떻게 구할 것인가? (규칙찾기)

 

 1) 예를들어, 1층 2호에 사는 사람의 수를 구할 때 두가지 방법이 있다. (다른 방법도 있겠지만 일단 내가 파악한 바로는)

 

1번 방법

 첫번째는 문제에서 주어진 대로 아래층 사람들을 내가 살고싶은 호수 까지 더하는 방법

 

 

2번 방법

 

 두번째는 내가 살고싶은 호수 바로 앞 호의 사람수와 아래층 사람수를 더하는 것. 

 이 로직은 층과 호수를 좀더 많이 그려놓고 봤을 때 보였다. (위에는 예시를 간단하게 하기 위해 숫자를 줄임)

 이 로직을 이용하면 각 호수에 사는 사람들의 수를 구하는 로직을 세울 수 있다.

 

k층 n호에 거주하는 사람의 수 = k층 n-1호 사람수 + k-1층 n호 사람수

 

 그렇다면, 이걸 어떻게 코드로 구현 할 것인가?

여기서 바로 렉이 걸렸다. 로직까지는 구했는데 그래서 코드를 어떻게 짜야하지..?

그래서 찾아봤다.

바로, 코드로 stack을 쌓는 것이다.

 

 

이중배열 이용해서 stack쌓기!

let arr = [
2: [1, 4, 10]
1: [1, 3, 6]
0: ['1, 2, 3]
]

 

여기서 사용된 것이 바로 이중배열이다.

자바스크립트의 이중배열은 소오오올직하게 '이중배열'이라고 이야기 할 수 없다.

그래서 array[1][2] 이런 식으로 직접 이중배열을 못 만들고 마치 이중배열인 것 처럼 흉내를 내줘야 한다.

 

일단 검색해서 알아본 방법은 4가지가 있다.  https://gent.tistory.com/296

위 코드에서는 배열을 만들어서 그 배열 안에 요소를 다시 배열롤 넣는 방법을 썼다. https://dpsc615.tistory.com/98

 

 

그래서 어떻게 푸나 하면, 해당 배열에서 위 식에 따라 값을 가져온다. 만약 예시처럼 1층 2호에 사는 사람의 수를 가져온다고 치면 index 1 배열의 2번째 요소를 불러오면 된다. 바로 Arr[1][2] 이렇게 말이다.

 

 

이 부분을 이해하는데 좀 오래걸렸다.

막 이 문제 설명해주신 블로거님은 쉬운문제라고 얘기하는데 그 말을 볼 때마다 '아.. 난 안쉽던데..'라며 현타가 오기도 했지만 그래도 덕분에 해당 문제를 끝까지 잘 이해할 수 있었다. 그리고 중요한건 코드! 코드도 직접 작성해봤다.

 

바로 답을 보는건 좋지 않지만, 시간을 많이 쏟아도 모를 땐 뛰어난 분들의 도움을 받도록 하자.