(6) [C++, Java] 백준 No.2193 : 이친수

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-7-DP-문제-풀이6-백준-No0000-카?category=864321

 

# C++(Top-down방식)

#include <iostream>

using namespace std;

long long d[91] = {0};

long long getTwoChinNum(int n)
{
    if ( n <= 2)
        return 1;

    else if (d[n] > 0)
        return d[n];

    else 
        d[n] = getTwoChinNum(n-1) + getTwoChinNum(n-2);
        return d[n];
}

int main()
{
    int n;
    cin >> n;
    
    d[1] = 1;
    d[2] = 1;
    
    cout << getTwoChinNum(n);
}

# C++(Bottom-up방식)

#include <iostream>

using namespace std;

long long d[91] = {0};

int main() {
    int n;
    cin >> n;
    
    d[1] = 1;
    d[2] = 1;
    
    for (int i=3; i<=n; i++)
        d[i] = d[i-1] + d[i-2];

    cout << d[n] << '\n';
}

# C++(Bottom-up방식)

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    long long d[91][2] = {{0, 0}, {0, 0}, {1, 0}};

    if (n <= 2)
        cout << 1 << "\n";

    else
    {
        for (int i = 3; i <= n; i++)
        {
            d[i][0] = d[i-1][0] + d[i-1][1];
            d[i][1] = d[i-1][0];
        }

        cout << d[n][0] + d[n][1] << "\n";
    }
}

# Java

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] d = new long[n+1];
        d[1] = 1;
        if (n >= 2) {
            d[2] = 1;
        }
        for (int i=3; i<=n; i++) {
            d[i] = d[i-1] + d[i-2];
        }
        System.out.println(d[n]);
    }
}