[프로그래머스 Level 2] 3 x n 타일링

2024.11.161분 읽기

문제 풀러 가기

풀이 1: 음수 값 발생 → 실패 ❌

function solution(n) {
    if (n % 2) return 0;
 
    const modular = 1000000007;
    const table = new Array(n+1).fill(0);
 
    table[0] = 1;
    table[2] = 3;
 
    for (let i = 4; i <= n; i += 2) {
        // ✅ 뺄셈 결과 음수 발생 가능
        table[i] = (4 * table[i - 2] - table[i - 4]) % modular;
    }
 
    return table[n];
}

풀이 2: 음수 값 방지 처리

function solution(n) {
    if (n % 2) return 0;
 
    const modular = 1000000007;
    const table = new Array(n+1).fill(0);
 
    table[0] = 1;
    table[2] = 3;
 
    for (let i = 4; i <= n; i += 2) {
        // ✅ (x + modular) % modular는 항상 0 ~ modular−1 범위에 값을 보장
        table[i] = (4 * table[i - 2] - table[i - 4] + modular) % modular;
    }
 
    return table[n];
}

풀이 3: Top-Down 방식

function solution(n) {
    if(n % 2) return 0;
 
    const modular = 1000000007;
    const table = new Array(n+1).fill(0);   // ✅ Memoization
 
    table[0] = 1;
    table[2] = 3;
 
    function calc(n){
        if (table[n] > 0) return table[n];
        return table[n] = (4 * calc(n-2) - calc(n-4) + modular) % modular;
    }
 
    return calc(n);
}

Review

제한사항
- 가로의 길이 n은 5,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

점화식 설명

f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2 + 2

점화식을 기반으로 가로 길이가 6인 직사각형을 채우는 방법의 수를 계산하면 다음과 같이 구할 수 있다.

예시: n=6일 때

f(4) * 3 + f(2) * 2 + 2
- f(4) = 11, f(2) = 3이므로
- f(6) = 11*3 + 3*2 + 2 = 33 + 6 + 2 = 41

점화식을 통해 구한 답을 증명하기 위해, 직사각형을 채우는 조합을 다음과 같이 세 부분으로 나누어 계산 과정을 설명할 수 있다.

① f(n-2) * 3

직전의 타일링 조합의 수(f(n-2))에 새로 추가된 가로 길이 2를 채우는 경우의 수(f(2) = 3)를 곱하여 확장된 조합의 수를 구한다.

② + f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2

n이 4 이상일 경우에만 계산되며, n이 4보다 작으면 의미가 없기 때문에 계산에서 제외된다.

n >= 4 부터는 이전 n들의 조합으로 만들 수 없는 특수한 조합, 즉, 고유 모양(입출력 예 #1의 마지막 2개의 조합과 같은)이 발생하고, n >= 6 부터는 이전 고유 모양과 새로 추가된 가로 길이 2를 채우는 조합 간의 대칭적 배치를 고려하여 경우의 수를 추가하는 것이 필요하다.

③ + 2

마지막으로 새롭게 발생한 고유 모양의 수 2를 더한다.

점화식 간략화

f(n) = 4 * f(n-2) - f(n-4)

n	result
2	3
4	11
6	41
8	153

점화식의 f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2 + 2 는 대칭적 배치를 고려하여 추가된 조합의 수를 계산하기 위한 항으로, 직전의 조합의 수(f(n-2))에서 이전의 조합의 수(f(n-4))를 뺀 값과 반복적으로 동일하다는 규칙을 발견할 수 있다.

점화식을 다시 정리하면, f(n) = f(n-2) * 3 + f(n-2) - f(n-4) 로 나타낼 수 있으며, 이를 간략화하면, f(n) = 4 * f(n-2) - f(n-4) 라는 최종 점화식을 얻을 수 있다.

DP8편 중 8번째

2025.01.084분 읽기
소수 구하기
소수 판별법과 소수를 구하는 알고리즘을 정리합니다.
- algorithm
- javascript
2025.01.061분 읽기
[프로그래머스 Level 2] 미로 탈출
프로그래머스 미로 탈출을 BFS로 풀이합니다.
- algorithm
- javascript
2025.01.051분 읽기
[프로그래머스 Level 2] 마법의 엘리베이터
프로그래머스 마법의 엘리베이터를 자리수 그리디로 풀이합니다.
- algorithm
- javascript

← 모든 글

[프로그래머스 Level 2] 3 x n 타일링

2024.11.161분 읽기

문제 풀러 가기

풀이 1: 음수 값 발생 → 실패 ❌

function solution(n) {
    if (n % 2) return 0;
 
    const modular = 1000000007;
    const table = new Array(n+1).fill(0);
 
    table[0] = 1;
    table[2] = 3;
 
    for (let i = 4; i <= n; i += 2) {
        // ✅ 뺄셈 결과 음수 발생 가능
        table[i] = (4 * table[i - 2] - table[i - 4]) % modular;
    }
 
    return table[n];
}

풀이 2: 음수 값 방지 처리

function solution(n) {
    if (n % 2) return 0;
 
    const modular = 1000000007;
    const table = new Array(n+1).fill(0);
 
    table[0] = 1;
    table[2] = 3;
 
    for (let i = 4; i <= n; i += 2) {
        // ✅ (x + modular) % modular는 항상 0 ~ modular−1 범위에 값을 보장
        table[i] = (4 * table[i - 2] - table[i - 4] + modular) % modular;
    }
 
    return table[n];
}

풀이 3: Top-Down 방식

function solution(n) {
    if(n % 2) return 0;
 
    const modular = 1000000007;
    const table = new Array(n+1).fill(0);   // ✅ Memoization
 
    table[0] = 1;
    table[2] = 3;
 
    function calc(n){
        if (table[n] > 0) return table[n];
        return table[n] = (4 * calc(n-2) - calc(n-4) + modular) % modular;
    }
 
    return calc(n);
}

Review

제한사항
- 가로의 길이 n은 5,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

점화식 설명

f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2 + 2

점화식을 기반으로 가로 길이가 6인 직사각형을 채우는 방법의 수를 계산하면 다음과 같이 구할 수 있다.

예시: n=6일 때

f(4) * 3 + f(2) * 2 + 2
- f(4) = 11, f(2) = 3이므로
- f(6) = 11*3 + 3*2 + 2 = 33 + 6 + 2 = 41

점화식을 통해 구한 답을 증명하기 위해, 직사각형을 채우는 조합을 다음과 같이 세 부분으로 나누어 계산 과정을 설명할 수 있다.

① f(n-2) * 3

직전의 타일링 조합의 수(f(n-2))에 새로 추가된 가로 길이 2를 채우는 경우의 수(f(2) = 3)를 곱하여 확장된 조합의 수를 구한다.

② + f(n-4) * 2 + f(n-6) * 2 + ... + f(2) * 2

n이 4 이상일 경우에만 계산되며, n이 4보다 작으면 의미가 없기 때문에 계산에서 제외된다.

③ + 2

마지막으로 새롭게 발생한 고유 모양의 수 2를 더한다.

점화식 간략화

f(n) = 4 * f(n-2) - f(n-4)

n	result
2	3
4	11
6	41
8	153

점화식을 다시 정리하면, f(n) = f(n-2) * 3 + f(n-2) - f(n-4) 로 나타낼 수 있으며, 이를 간략화하면, f(n) = 4 * f(n-2) - f(n-4) 라는 최종 점화식을 얻을 수 있다.

DP8편 중 8번째

2025.01.084분 읽기
소수 구하기
소수 판별법과 소수를 구하는 알고리즘을 정리합니다.
- algorithm
- javascript
2025.01.061분 읽기
[프로그래머스 Level 2] 미로 탈출
프로그래머스 미로 탈출을 BFS로 풀이합니다.
- algorithm
- javascript
2025.01.051분 읽기
[프로그래머스 Level 2] 마법의 엘리베이터
프로그래머스 마법의 엘리베이터를 자리수 그리디로 풀이합니다.
- algorithm
- javascript

← 모든 글

[프로그래머스 Level 2] 3 x n 타일링

풀이 1: 음수 값 발생 → 실패 ❌

풀이 2: 음수 값 방지 처리

풀이 3: Top-Down 방식

Review

점화식 설명

점화식 간략화

DP8편 중 8번째

관련 글

소수 구하기

[프로그래머스 Level 2] 미로 탈출

[프로그래머스 Level 2] 마법의 엘리베이터

댓글

[프로그래머스 Level 2] 3 x n 타일링

풀이 1: 음수 값 발생 → 실패 ❌

풀이 2: 음수 값 방지 처리

풀이 3: Top-Down 방식

Review

점화식 설명

점화식 간략화

DP8편 중 8번째

관련 글

소수 구하기

[프로그래머스 Level 2] 미로 탈출

[프로그래머스 Level 2] 마법의 엘리베이터

댓글

[프로그래머스 Level 2] 3 x n 타일링

풀이 1: 음수 값 발생 → 실패 ❌

풀이 2: 음수 값 방지 처리

풀이 3: Top-Down 방식

Review

점화식 설명

점화식 간략화

DP · 8편 중 8번째

관련 글

소수 구하기

[프로그래머스 Level 2] 미로 탈출

[프로그래머스 Level 2] 마법의 엘리베이터

댓글

[프로그래머스 Level 2] 3 x n 타일링

풀이 1: 음수 값 발생 → 실패 ❌

풀이 2: 음수 값 방지 처리

풀이 3: Top-Down 방식

Review

점화식 설명

점화식 간략화

DP · 8편 중 8번째

관련 글

소수 구하기

[프로그래머스 Level 2] 미로 탈출

[프로그래머스 Level 2] 마법의 엘리베이터

댓글

DP8편 중 8번째

DP8편 중 8번째