쾌락없는 책임 (공부)/알고리즘 문제풀이
[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 에서의 경우의수를 더하면 구할 수 있으며 순열문제 같은거라 생각하면 편합니다.
반응형