[프로그래머스] 코딩테스트 연습 - 연습문제 Level 4 3 x n 타일링

uoahy·2021년 10월 7일
0

Solution.java

import java.math.BigInteger;

class Solution {
    public int solution(int n) {
        if (n % 2 == 1) return 0;
        
        BigInteger[] dp = new BigInteger[n + 1];
        dp[0] = new BigInteger("1"); dp[2] = new BigInteger("3");
        BigInteger four = new BigInteger("4");
        for (int i = 4; i <= n; i += 2) {
            dp[i] = dp[i - 2].multiply(four).subtract(dp[i - 4]);
        }
        
        return dp[n].remainder(new BigInteger("1000000007")).intValue();
    }
}

규칙을 못 찾고있다가 어떤 분의 풀이를 보고 처음 몇 개는 완전탐색을 통해서 값을 구한 후 규칙을 찾는 방식을 통해 규칙을 찾게되었다.

하지만 그 뒤에 나머지 연산에서 막혀 BigInteger를 사용하게되었다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

0개의 댓글