π£ λ¬Έμ μ΄ν΄
1. 첫 λ²μ§Έ μλ¦¬κ° 1λ‘ μμνλ μμ΄λ€.
2. 1κ³Ό 1μ΄ μΈμ ν μ μλ€κ³ νμΌλ, λ λ²μ§Έ μ리λ 0 μ΄λ€.
3. N μλ¦Ώμ μ€μμ μ΄λ¬ν κ·μΉμ λ§μ‘±νλ μμ κ°μλ₯Ό ꡬν΄μΌ νλ€.
λμ κ³νλ²(Dynamic Programming) λ°©μμ μ¬μ©νλ€.
π νμ΄ κ³Όμ
N = 1 μΈ κ²½μ°λ 1 νλλ°μ μλ€. => 1
N = 2 μΈ κ²½μ°λ 10 νλλ°μ μλ€. => 1
N = 3 μΈ κ²½μ°λ 100, 101 λ κ°μ§μ΄λ€. => 2
N = 4 μΈ κ²½μ°λ 1000, 1001, 1010 μΈ κ°μ§μ΄λ€. => 3
N = 5 μΈ κ²½μ°λ 10000, 10001, 10010, 10100, 10101 λ€μ― κ°μ§μ΄λ€. => 5
μ΄ κ·μΉμ ν λλ‘ λ°κ²¬ν μ μλ κ²μ
1) λ°λ‘ μ μΌμ΄μ€μ λ°λΌ λ€μ μΌμ΄μ€κ° μ ν΄μ§λ€κ³ λ³Ό μ μλ€.
N = 3 μΌ λμ 100μμ λ€μ 0 λλ 1 μ λΆμΌ μ μκ³ 101 μμ λ€μ 0 μ λΆμΌ μ μλ€. μ΄κ²μ΄ N = 4 μΌ λμ μ’ λ₯
2) κ°μμ λ³νκ° νΌλ³΄λμΉμ λμΌνλ€.
μ΄ λ κ°μ§ λ°©μμΌλ‘ μμ€μ½λ μμ±μ ν΄λ³΄μλ€.
<1 λ² μμ€μ½λ>
μμ± μΈμ΄: C++
#include <cstdio>
long dp[100][2] = {0, }; // 0 λ²μ§Έ μ΄μ΄ 0μΌλ‘ λλλ κ²½μ°, 1 λ²μ§Έ μ΄μ΄ 1λ‘ λλλ κ²½μ°
void solve(int num){
dp[1][0] = 0; dp[1][1] = 1;
for (int i = 2; i <= num; ++i) {
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
}
int main(){
int nCount = 0;
scanf("%d", &nCount);
solve(nCount);
printf("%ld\n", dp[nCount][0] + dp[nCount][1]);
return 0;
}
μ§μ λͺ κ°μ§ μΌμ΄μ€λ₯Ό μ μ΄λ³΄λ€λ³΄λ©΄ λ°κ²¬νκ² λλ κ·μΉμ΄ μλ€.
0 μΌλ‘ λλλ μλ κ·Έ λ€μ μΌμ΄μ€μ 0 μΌλ‘ λλλ μ, 1 λ‘ λλλ μ λ κ°μ§λ₯Ό λ§λ€ μ μλ€λ κ²μ΄κ³ ,
1 λ‘ λλλ μλ κ·Έ λ€μ μΌμ΄μ€μ 0 μΌλ‘ λλλ μ ν κ°μ§λ§ λ§λ€ μ μλ€λ κ²μ΄λ€.
μ΄λ₯Ό ν΅ν΄ μ νμμ μμ±νλ©΄ λ€μκ³Ό κ°λ€.
dp[i][0] μ i μ리 μ«μμμ 0 μΌλ‘ λλλ μμ κ°μμ΄κ³ dp[i][1] μ i μ리 μ«μμμ 1 λ‘ λλλ μμ κ°μμ΄λ€.
dp[i][0] = dp[i-1][0] + dp[i-1][1] => 0 μΌλ‘ λλλ μμ 1 λ‘ λλλ μ λͺ¨λ 곡ν΅μ μΌλ‘ 0 μΌλ‘ λλλ μλ₯Ό λ§λ€ μ μλ€.
dp[i][1] = dp[i-1][0] => 0 μΌλ‘ λλλ μλ§ 1 λ‘ λλλ μλ₯Ό λ§λ€ μ μλ€.
<2 λ² μμ€μ½λ>
μμ± μΈμ΄: C++
#include <cstdio>
long dp[100] = {0, };
void solve(int num){
dp[1] = dp[2] = 1;
for (int i = 3; i <= num; ++i) {
dp[i] = dp[i-2] + dp[i-1];
}
}
int main(){
int nCount = 0;
scanf("%d", &nCount);
solve(nCount);
printf("%ld\n", dp[nCount]);
return 0;
}
νΌλ³΄λμΉ λ°©μ νμ΄μ΄λ€.
π λ°°μ΄ μ
dp λ¬Έμ μ€ κ°λ¨ν νΈμ μνλ λ¬Έμ μ΄λ,
λ κ°μ§ νμ΄λ‘ μ κ·Όν μ μλ κ²μ μλν΄λ³΄μμ κ°μΈμ μΌλ‘ μ’ λΏλ―ν νμ΄μλ κ² κ°λ€