728x90

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]);
}
 

+ Recent posts