[프로그래머스] 2xn 타일링 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(n) {
    const arr = [...Array(n)].map((v, i) => i) // n = 3까지는 idx값과 동일
    for (let i = 4; i <= n; i += 1) arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007
    return arr[n]
}

 

구현 로직

이 문제는 예전에 비슷한 문제를 풀었던 기억이 있는데 상향식 DP로 메모이제이션 해가며 푸는 방법이 있습니다. 어레이 arr는 idx값으로 초기화해줬는데 큰 의미는 없고 n이 3까지는 결과가 idx값과 동일하기 때문입니다. arr = [0, 1, 2, 3]으로 초기화 해줘도 될 것 같네요.

 

n = 4부터는 값이 커집니다. 타일이 1개 추가될 때마다 2가지 케이스를 경우의 수에 더해줘야 합니다.

 

첫번째로, 이전 타일 개수(n = 4 - 1일때)로 만들었던 경우만큼 추가됩니다. n = 3일 때 나왔던 방법들에 타일이 하나 추가되었으니 n = 3일때 나온 수만큼 추가가 되겠죠.

두번째로, 그 이전 타일 개수(n = 4 - 2일때)로 만들었던 경우도 추가해줘야 합니다. 왜냐하면 그 이전 타일에다가 가로로 2개 놓은 ( = ) 케이스를 고려해줘야 하기 때문이죠. 그러면 세로로 2개 놓은 ( || ) 케이스도 추가해줘야 하는 것 아니냐 할 수 있는데 이미 n = 4 - 1 일 때 추가가 되었으니 중복됩니다.

 

따라서 메모이제이션 할 점화식은 다음과 같이 됩니다.

arr[i] = arr[i - 1] + arr[i - 2], { i >= 4 }