코딩 테스트 8일차

다리 놓기 재 도전 !! 

 

문제 : 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

규칙 찾기 :

d[1][1] = 1 d[1][2] = 2 d[1][3] = 3 d[1][4] = 4 d[1][5] = 5

d[2][1] = 0 d[2][2] = 1 d[2][3] = 3 d[2][4] = 6 d[2][5] = 10

d[3][1] = 0 d[3][2] = 0 d[3][3] = 1 d[3][4] = 4 d[3][5] = 10

 

d[3][5] = d[2][4] + d[2][3] + d[2][2] 이다 

d[2][4] = d[1][3] + d[1][2] + d[1][1] 이다 

d[3][5] = (d[1][3] + d[1][2] + d[1][1]) +  d[2][3] + d[2][2]

 

이렇게 되는 것을 알았고 규칙을 찾기 위해 우선 가장 작은 수부터 하나씩 그려보는 것도 중요

// 백준 1010 문제
const fs = require("fs");
// let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const input = ["3","2 2","1 5","13 29"];
let inputArr = [];
for (let i = 1; i < input.length; i++) {
    const element = input[i];
    inputArr.push(element.split(" "));
}


for (let i = 0; i < inputArr.length; i++) {
    
}
inputArr.forEach(el =>{
    const n = + el[0];
    const m = + el[1];
    // const memo = Array.from(Array(30), () => Array(30).fill(0));
    let memo   = Array.from(Array(30), () =>Array(30).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if(i === j){
                // d[1][1] = 1 , d[2][2] = 1 , d[3][3] = 1
                memo[i][j] = 1;
            }else if(i === 1){
                // d[1][2] = 2 d[1][3] = 3 d[1][4] = 4 d[1][5] = 5
                memo[i][j] = j;
            }else{
                let temp = 0;
                // d[3][5] = d[2][4] + d[2][3] + d[2][2] 이다 
                // d[2][4] = d[1][3] + d[1][2] + d[1][1] 이다 
                // d[3][5] = (d[1][3] + d[1][2] + d[1][1]) +  d[2][3] + d[2][2]
                for (let k = 0; k < j; k++) {
                    temp += memo[i-1][k];
                }
                memo[i][j] = temp;
            }
            
        }
    }
    console.log(memo[n][m]);

});

 

 

 

이제 다시 2000번을 푸는 방법을 찾아 봐야 겠습니다. 

이상이었습니다