문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
2
Plain Text
복사
예제 출력 1
2
Plain Text
복사
예제 입력 2
9
Plain Text
복사
예제 출력 2
55
Plain Text
복사
My solution
1x2와 2x1 타일을 가지고 규칙을 찾아보면
10007로 나눈 나머지를 반환하고, 자료형 크기 초과를 막기 위해 반복문에서 값을 할당할 때마다 매번 나누는 연산을 해준다.
그림으로 경우의 수 구하면 실수가 있을 수 있지 않나?
규칙 찾는 데 체계적인 접근법이 있나
Code
function solution(i) {
const N = i.toString().trim() * 1;
const DP = Array.from({ length: N + 1 }, () => 0);
DP[1] = 1;
DP[2] = 2;
for (let i = 3; i <= N; i++) {
DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
}
console.log(DP[N]);
return DP[N];
}
describe('2xn 타일링', () => {
it('TC1', () => {
expect(solution(`2`)).toStrictEqual(2);
});
it('TC2', () => {
expect(solution(`9`)).toStrictEqual(55);
});
});
JavaScript
복사
