프로그래머스_2*n 타일링

https://programmers.co.kr/learn/courses/30/lessons/12900#

코딩테스트 연습 - 2 x n 타일링 | 프로그래머스

기본적인 DP 문제이다.

Level 3의 카카오 추석 트래픽 문제를 풀다가 멘탈이 나가서 쉬어갈 겸 쉬운 문제를 찾고 있었다.

그러다 Level 3에 2*n 타일링 문제가 있길래 풀어봤다.

기본적인 DP 문제로 점화식을 세우면 손쉽게 해결이 가능하였다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// DP로 vector에서 이전 값에다 추가할 수 있는 경우의 수 더해주기
int solution(int n) {
    int answer = 0;
    vector<long long> v(n+1,0);
    v[1]=1, v[2]=2; // 초기화
    for(int i=3;i<=n;i++){
        // -1 경우와 -2 경우의 수 더해주기
        v[i] = (v[i-1] + v[i-2]) % 1000000007;;
    }
    answer = v[n];
    return answer;
}