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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

전형적인 동적계획법 문제이다.
i번째 타일은 i-1번 째 타일 모양에 타일을 하나 더 채워서 만들 수 있다.
그리고 i-2번 째 타일 모양에 타일 2개를 더 채워서 만들 수 있는데, 타일 2개를 채우는 방법은 2가지이다.
여기서 dp[i] = dp[i-1] + 2 * dp[i-2] 라고 생각할 수 있는데, i-2번째 타일에 2개 더 채우는 방법 중에서 1가지 방법은 i-1번째 타일에 1개의 타일을 추가하는 방법과 중복되므로 dp[i] = dp[i-1] + dp[i-2]가 된다.
따라서 해당 점화식으로 해결할 수 있다.

코드

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;

vector<int> dp;

int solve(int idx){
    int& ret = dp[idx];
    if(ret != -1) return ret;
    if(idx == 1) return ret = 1;
    if(idx == 2) return ret = 2;
    return ret = (solve(idx-1) + solve(idx-2)) % MOD;
}

int solution(int n) {
    int answer = 0;
    dp = vector<int>(n+1, -1);
    return solve(n);
}