11726 - 2xn 타일링
처음에 완전 탐색으로 문제를 풀었다가 시간초과가 났다.
그래서 DP로 접근해서 문제를 풀었다.
D[N]= N칸을 채우는 경우의 수
라고 점화식을 세우고 문제를 풀었다.
<정답 코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include<iostream> #include<string.h> using namespace std; int D[1001]; int n; int go(int N) { if (N < 0) { return 0; } if (N == 0) { return 1; } if (D[N] != -1) { return D[N]; } D[N] = (go(N - 1) + go(N - 2))%10007; return D[N]; } int main() { cin >> n; memset(D, -1, sizeof(D)); go(n); cout << D[n] << endl; return 0; } | cs |
반응형