프로그래머스 Lv.2 3 x n 타일링 (Java / Python)

eora21·2022년 9월 12일

알고리즘 프로그래머스

프로그래머스

목록 보기

23/38

문제 링크

문제 간단 해석

규칙 찾기 문제. 의외로 까다롭다.

Java

풀이 코드

class Solution {
    public int solution(int n) {
        if (n % 2 == 1)
            return 0;

        int past = 0, before = 1;
        long answer = 1;
        n >>= 1;

        for (int i = 0; i < n; i++) {
            past = before;
            before = (int)answer;
            answer = (4 * answer - past) % 1000000007;
        }

        return (int)answer + (answer >= 0 ? 0 : 1000000007);
    }
}

해석

if (n % 2 == 1)
    return 0;

짝수가 아니라면 0 반환. 홀수라면 공간을 채울 수 없다.

int past = 0, before = 1;
long answer = 1;
n >>= 1;

2차례 전의 값 past, 1차례 전의 값 before, 현재값 answer 선언. answer는 값 변환 이슈가 있어 long으로 선언했다.
n을 2로 나눠(비트 n번 이동 == 2^n으로 나눔) 계산의 편의를 더했다.

for (int i = 0; i < n; i++) {
    past = before;
    before = (int)answer;
    answer = (4 * answer - past) % 1000000007;
}

해당 식을 이해하기 위해선 먼저 규칙을 찾아야 한다.
먼저 n에 2칸이 주어졌다고 생각하자. 경우의 수는 3이다. 생각하기 쉽게 f(2) = 3으로 두자. 이는 특정 칸이 주어졌을 때, 만들 수 있는 경우의 수라고 하자.
4가 주어진다면, 앞선 경우의 수(f(2)) * 나머지 2칸의 경우의 수(3) + 4칸으로 만들 수 있는 특이 케이스(2)로 정의할 수 있다.

특이 케이스란 예제에서 확인할 수 있는 이 2가지인데, 이는 n이 몇이든 무조건 2가지만 생성된다.

정리하자면, f(4) = 3f(2) + 2이다.
6칸은 앞선 경우의 수(f(4)) 나머지 2칸의 경우의 수(3) + 2칸 먼저 차지(f(2)) 4칸의 특이 케이스(2) + 6칸의 특이 케이스(2) => f(6) = 3f(4) + 2f(2) + 2이다.
8칸도 마찬가지로 f(8) = 3f(6) + 2f(4) + 2f(2) + 2로 표현할 수 있다.

한 번에 정리해보겠다.

f(2) = 3
f(4) = 3f(2) + 2
f(6) = 3f(4) + 2f(2) + 2
f(8) = 3f(6) + 2f(4) + 2f(2) + 2
f(10) = 3f(8) + 2f(6) + 2f(4) + 2f(2) + 2
...
f(2n) = 3f(2n - 2) + 2f(2n - 4) + ... + 2f(2n - 2k) + 2

이 때, f(8)과 f(6)을 자세히 보자.
f(8) = 3f(6) + 2f(4) + 2f(2) + 2에서 2f(4) + 2f(2) + 2의 형태가 꼭 f(6) = 3f(4) + 2f(2) + 2과 닮지 않았는가?
f(6)에서 f(4)를 뺀 값과 같다!
즉, f(8)을 다시 정의하자면 f(8) = 3f(6) + 2f(4) + 2f(2) + 2 = 3f(6) + f(6) - f(4) = 4f(6) - f(4)로 표현할 수 있다.
따라서 식을 다시 정리하자면

f(-2) = 1 (식의 규칙을 맞추기 위한 초기값)
f(0) = 1 (식의 규칙을 맞추기 위한 초기값)

f(2) = 4f(0) - f(-2)
f(4) = 4f(2) - f(0)
f(6) = 4f(4) - f(2)
f(8) = 4f(6) - f(4)
f(10) = 4f(8) - f(6)
...
f(2n) = 4f(2n - 2) - f(2n - 4)

로 더 쉽게 표현할 수 있다.

위에서 정의한 변수로 표현한다면 answer = (4 * before - past)가 될 것이다.
그러나, before의 최대값은 1000000007의 나머지이니 1000000006이 된다.
4로 곱하면 int의 범위를 넘어버려 overflow가 일어난다.
따라서 long인 answer로 수식을 완성하고, 1000000007로 나눠주자.

return (int)answer + (answer >= 0 ? 0 : 1000000007);

past가 1000000007에 가까운 값이고, before이 0에 가까운 값이었다면 answer은 음수가 나올 수 있다. 음수일 때는 1000000007을 더해 본래 표현될 값을 찾게끔 하자.

Python

풀이 코드

def solution(n):
    if n % 2:
        return 0
    
    answer = 0
    for i in range(n // 2 + 1):
        one = n - (2 * i)
        two = i
        min_cnt = min(one, two)
        
        A = B = 1
        for j in range(min_cnt):
            A *= n - i - j
            B *= j + 1
        answer += A // B * (2 ** (one // 2))
            
    return answer % 1000000007