[프로그래머스] 2 x n 타일링, java

- 문제

프로그래머스

- 풀이

class Solution {
    
    //dp 접근해보았습니다.
    //직접 1~5까지의 경우의 수를 구해본다면 다음과 같은 흐름을 보여줍니다.
    /*
    1 - 1 |
    2 - 2 ||, =
    3 - 3 |||, |=, =|
    4 - 5 ||||, ||=, |=|, =||, ==
    5 - 8 |||||, |||=, ||=|, |=||, =|||, |==, =|=, ==|
    */
    
    //위의 값을 보며 규칙을 찾아 보았을 때, dp[i] = dp[i-1]+dp[i-2] 라는 규칙을 찾을 수 있습니다.
    //이를 통해 문제 풀이를 진행합니다.
    
    public int solution(int n) {
        
        //dp를 담을 int 배열을 만들어줍니다. n까지의 크기를 구해야하므로
        //n+1의 크기를 부여해줍니다.
        int[] dp = new int[n+1];
        
        //시작이 되는 dp[1]과 dp[2]의 값은 이미 알고 있으므로 미리 담아줍니다.
        dp[1] = 1;
        dp[2] = 2;
        
        //위에서 찾아낸 규칙에 따라 dp[i]를 채워줍니다.
        //그리고 문제에서 주어진 조건에 따라 1,000,000,007의 계산을 추가해줍니다. (모듈러 분배 법칙)
        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1]+dp[i-2])%1000000007;
        }
        
        //dp[n]이 답이므로 반환해줍니다.
        return dp[n];
    }
}