쾌락없는 책임 (공부)/알고리즘 문제풀이

[Algorithm] 프로그래머스 2 x n 타일링, C++, DP

허스크 2022. 2. 23. 15:32
반응형

 

코딩테스트 연습 - 2 x n 타일링

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는

programmers.co.kr

#include <string>
#include <vector>

using namespace std;
const int mod = 1000000007;
int solution(int n) {
    int answer = 0;

    vector<int> wayCount(n+1);
    wayCount[0] = 0;
    wayCount[1] = 1;
    wayCount[2] = 2;

    for(unsigned i = 3; i <= n; i++){
        wayCount[i] = (wayCount[i-1] + wayCount[i-2])%mod;
    }

    return answer = wayCount[n];
}

DP 문제들 중에서 닳고 닳은 문제라 큰 설명은 필요 없을 것 같습니다. 단순히 i-1 에서의 경우의 수, i-2 에서의 경우의수를 더하면 구할 수 있으며 순열문제 같은거라 생각하면 편합니다.

반응형