[Java] 2 x n 타일링

프로그래머스

 

문제 풀이

 

처음엔 단순히 dfs를 생각했다가 경우의 수가 많아질 수 있다와 1칸, 2칸 ~ N칸 늘어나게 되더라도 몇 칸마다 채워주는 규칙은 똑같지 않나? 라는 생각에 DP가 떠올랐다. 점화식 구하는 것은 DP 문제 중에 기초 중에 기초였지만 경우의 수를 1,000,000,007로 나누는 것을 DP 배열에 저장할 때 모두 해줘야 했다. 앞으로 저런 제한사항이 있다면 주의해서 과정에 꼭 넣는 것을 빼먹지 말아야겠다.

 

public class 타일링_2xn {
    public int solution(int n) {
        int answer = 0;

        int[] DP = new int[n + 1];

        DP[0] = 0;
        DP[1] = 1;
        DP[2] = 2;

        for (int i = 3; i <= n; i++) {
            int num = DP[i-1] + DP[i-2];
            DP[i] = num  % 1000000007;
        }

        answer = DP[n];

        return answer;
    }
}