[프로그래머스] Lv2. 2 x n 타일링

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12900?language=java

프로그래머스

코드

def solution(n):
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = (dp[i-1] + dp[i-2])%1000000007
    return dp[n]

class Solution {
    public int solution(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2])%1000000007;
        }
        return dp[n];
    }
    
}

풀이

• 한 칸에 대해서는 타일을 세로로 세운 것밖에 더할 수 없으므로, i-1의 인덱스값을 그대로 더해주면 된다.
• i-2의 인덱스의 값에서는, 2칸이므로 i-2의 인덱스의 값에 2를 곱한 값이라고 생각할 수 있지만, 위에 i-1의 인덱스의 값의 타일과 겹친 부분이 있으므로, 2를 곱하지 않고 더해준다.