Programmers[12900] - 2 x n 타일링[Level3]

링크

프로그래머스

 

문제설명

• 점화식, DP

문제풀이

• 피보나치수열
  • A_1 = 1 = |
  • A_2 = 2 = | |+〓
  • A_3 = 3 = | | | + | 〓 + 〓 |
  • ...
  • | 로 끝나는 경우는 | | , 〓 2가지 경우를 만들고
  • 〓로 끝나는 경우는 〓 | 1가지 경우를 만든다.
  • A_n = A_n-1 + A_n-2에서
  • A_n의 경우의 갯수 중
    • | 로 끝나는 경우의 갯수가 A_n-1이고
      • A_n-1의 모든 경우의 갯수에 |를 붙일 수 있으므로
    • 〓로 끝나는 경우의 갯수가 A_n-2이다
      
      • A_n-1의 |로 끝나는 경우의 갯수만큼 〓을 만들 수 있음
      • A_n-1의 |로 끝나는 경우의 갯수는 A_n-2임

 

문제코드

public class Solution {

    public static int solution(int n) {
        int div = 1000000007;
        int l = Math.max(n,2);
        long[] dp = new long[l+1];
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2])%div;
        }

        return (int)dp[n];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(i+":"+solution(i));
        }
    }
}

아쉬운점

• n x 3 타일링처럼 생각해서 n이 홀수인 경우 생각 안했었음.
• 그냥 피보나치였음 쉽게 풀 수 있었음

잘한점

• 왜 피보나치 수열의 점화식이 나왔는지 이해했음.