[Java] 프로그래머스(level-2) - 2xn 타일링

문제 풀이

---

이번 문제는 동적 계획법 DP를 이용해 손쉽게 풀 수 있다.

아아디어 도출

이 문제는 백준의 2×n 타일링 문제와 거의 유사한 문제이다.

문제의 자세한 풀이는 해당 문제와 거의 동일해서 위 링크를 참조하기 바란다. 간단히 문제 핵심 아이디어만 살펴보고 넘어가자.

2xn 타일링 문제는 피보나치 수열과 동일한 구조를 가지고 있기에 DP를 이용해 피보나치 수열을 DP 테이블에 갱신하면 된다.

1. DP를 이용해 피보나치 수열의 N번째 수를 피보나치 함수로 구현한다.
2. 이미 구한 N번째 수일 경우 바로 반환(메모이제이션)한다.

백준의 문제와 다른 점은 백준에서는 경우의 수 % 10,007 이었다면, 프로그래머스에서의 문제에서는 경우의 수 % 1,000,000,007의 차이만 있다고 보면 된다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    static int[] D;

    public int solution(int n) {

        D = new int[n+1];

        Arrays.fill(D, -1);

        D[0] = 1;
        D[1] = 1;

        return fibo(n);
    }

    public static int fibo(int N) {
        if(D[N] != -1) {
            return D[N];
        }
        return D[N] = (fibo(N-1) + fibo(N-2)) % 1000000007;
    }

    public static void main(String[] args) {
        
        Solution sol = new Solution();
        
        int n = 4;
        
        sol.solution(n);

    }

}

회고

-

---

출처

-

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.