μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
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 |
- μ λ ¬
- μμνμ
- λλΉμ°μ νμ
- νλ‘μ΄λμμ¬
- db
- DFS
- κ·Έλν
- κ·Έλνμνλ¬Έμ
- μν
- νλ‘κ·Έλλ¨Έμ€
- λ³ν©μ λ ¬
- DP
- ꡬν
- μ°μ μμν
- 11650
- Side Menu
- κ·Έλννμ
- LIS
- μκ³ λ¦¬μ¦
- λμ κ³νλ²
- λ¨Έμ§μνΈ
- λ€μ΄λλ―Ήνλ‘κ·Έλλ°
- λ°±μ€
- SQL
- BFS
- μλ£κ΅¬μ‘°
- κΉμ΄μ°μ νμ
- λ°μ΄ν°λ² μ΄μ€
- 그리λ
- μμꡬνκΈ°
πππ°πΈ π£πΆπ΅ π΄π΅π¦π’π₯πΊ
[λ°±μ€] 11727λ²: 2×n νμΌλ§ 2 - C++ λ³Έλ¬Έ
λ¬Έμ
2×n μ§μ¬κ°νμ 1×2, 2×1κ³Ό 2×2 νμΌλ‘ μ±μ°λ λ°©λ²μ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μλ κ·Έλ¦Όμ 2×17 μ§μ¬κ°νμ μ±μ΄ νκ°μ§ μμ΄λ€.
μ λ ₯
첫째 μ€μ nμ΄ μ£Όμ΄μ§λ€. (1 ≤ n ≤ 1,000)
μΆλ ₯
첫째 μ€μ 2×n ν¬κΈ°μ μ§μ¬κ°νμ μ±μ°λ λ°©λ²μ μλ₯Ό 10,007λ‘ λλ λλ¨Έμ§λ₯Ό μΆλ ₯νλ€.
DPλ₯Ό μ΄μ©νμ¬ νΈλ λ¬Έμ .
μμ νμλ 11726λ²μΈ 2xn νμΌλ§μ μ‘°κΈλ§ μμ©νλ©΄ λ°λ‘ ν μ μλ€.
κ°λ‘ ν μΉΈμ 1x2 νμΌλ‘ μ±μ°λ λ°©λ² ν κ°μ§, κ°λ‘ λ μΉΈμ 2x1 νμΌμ μμλλ‘ μμ μ±μ°λ λ°©λ² νλ, 2x2 νμΌλ‘ μ±μ°λ λ°©λ² νλμΈ μ μ κ³ λ €νμ¬ μ νμμ μΈμ°λ©΄ λ€μκ³Ό κ°λ€.
D[n] = D[n - 1] + 2 * D[n - 2]
μ΄ λ¬Έμ μμ μ΄κΈ°κ° μ€μ κ³Ό 맀 μ°μ°λ§λ€ 10007μ λλ¨Έμ§ μ°μ°μ ν΄μ£Όλ κ²μλ§ μ μνμ¬ νλ©΄ μ½κ² ν μ μλ€.
λ¬Έμ λ top-down λ°©μμΌλ‘ νμλ€.
μ½λ
#include <cstdio>
#include <vector>
#define MAX 1001
using namespace std;
vector<int> memo(MAX, 0);
int DP(int num);
int main(void) {
int num;
scanf("%d", &num);
printf("%d\n", DP(num));
return 0;
}
int DP(int num) {
if(num < 2) return 1;
if(memo[num] > 0) return memo[num];
int result = (DP(num - 1) + 2 * DP(num - 2)) % 10007;
memo[num] = result;
return result;
}
'μ½λ©ν μ€νΈ μ€λΉ > λ°±μ€' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 2156λ²: ν¬λμ£Ό μμ - C++ (0) | 2021.07.17 |
---|---|
[λ°±μ€] 9095λ²: 1, 2, 3 λνκΈ° - C++ (0) | 2021.07.16 |
[λ°±μ€] 11726λ²: 2Γn νμΌλ§ - C++ (0) | 2021.07.12 |
[λ°±μ€] 10814λ²: λμ΄μ μ λ ¬ - C++ (0) | 2021.07.11 |
[λ°±μ€] 1463λ²: 1λ‘ λ§λ€κΈ° - C++ (0) | 2021.07.10 |