11727 2xn 타일링2

My solution

규칙을 찾기 위해 그리는 과정에서 실수하면 규칙을 찾을 수 없다.

i-2번 인덱스의 직사각형에 1x2 타일을 2개 놓거나 2x2 타일을 1개 놓으면 i번 인덱스의 직사각형을 만들 수 있다.

또는 i-1번 인덱스의 직사각형에 2x1 타일을 1개 놓으면 i번 인덱스의 직사각형을 만들 수 있다.

따라서 DP[i] = DP[i - 1] + 2 * DP[i - 2]가 된다.

10007로 나눈 나머지를 반환하고, 자료형 크기 초과를 막기 위해 반복문에서 값을 할당할 때마다 매번 나누는 연산을 해준다.

Code

const solution = function (i) {
  const N = i.toString().trim() * 1;
  const DP = Array.from({ length: N + 1 }, () => 0);

  DP[1] = 1;
  DP[2] = 3;
  for (let i = 3; i <= N; i++) {
    DP[i] = (DP[i - 1] + 2 * DP[i - 2]) % 10007;
  }

  console.log(DP[N]);
  return DP[N];
};

describe('2xn 타일링 2', () => {
  it('TC1', () => {
    expect(solution(`2`)).toStrictEqual(3);
  });
  it('TC2', () => {
    expect(solution(`8`)).toStrictEqual(171);
  });
  it('TC3', () => {
    expect(solution(`12`)).toStrictEqual(2731);
  });
});
JavaScript
복사