2193 이친수

BOJ::2193 이친수

https://www.acmicpc.net/problem/2193

n자리 이친수가 될 수 있는 경우의 수를 구하는 dp문제.

--이친수--

1자리 : 1

2자리 : 10

3자리 : 100, 101

4자리 : 1000, 1001, 1010

.

.

.

n자리 : ?

10xxxxxxx : d[n-2]

1xxxxxxxx : n-1번째 이친수의 맨 앞자리를 0으로 바꾼 수만큼 올 수있다 -> d[n-1]

즉, d[n] = d[n-1]+d[n-2] 라는 점화식을 세울 수 있다.

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static long d[]=new long[91];
 
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        d[1]=1;
        for(int i = 2 ; i <= n ; i++){
            d[i]=d[i-1]+d[i-2];
        }
        System.out.println(d[n]);
    }
}

  

<C++>

#include <iostream>
using namespace std;
 
int n;
long d[91];
 
int main() {
    cin >> n;
    d[1] = 1;
 
    for (int i = 2; i <= n; i++) {
        d[i] = d[i - 1] + d[i - 2];
    }
    cout << d[n] << endl;
}