[BOJ]2193번: 이친수(java, c++)

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

2193번: 이친수

 

방법 1: Top-down

import java.io.*;
 
public class Main {
 
    public static long[] arrPinary;
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int iLength = Integer.parseInt(br.readLine());
            
            arrPinary = new long [iLength + 1];
            
            System.out.println(calculate(iLength));
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static long calculate (int length) {
        
        if(length <= 1 ) {
            return length;
        }
        
        if (arrPinary[length] > 0) {
            return arrPinary[length];
        }
        
        arrPinary[length] = calculate(length - 1) + calculate(length - 2);
        
        return arrPinary[length];
    }
}

 

방법 2: Bottom-up

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int iLength = Integer.parseInt(br.readLine());
            
            long[] arrPinary = new long [iLength + 1];
            
            arrPinary[1] = 1;
            
            for (int i = 2; i <= iLength; i++) {
                arrPinary[i] = arrPinary[i - 1] + arrPinary[i - 2];
            }
            
            System.out.println(arrPinary[iLength]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    const int MAX = 90;
    long long S[MAX + 1] = {0, 1, };
 
    int n;
    cin >> n;
 
    /*
    D[N][i] : i로 끝나는 N자리의 이친수라 할때,
 
            S[N] = D[N][0] + D[N][1]
            D[N][0] = D[N - 1][0] + D[N - 1][1]                   = S[N - 1]
            D[N][1] = D[N - 1][0] = D[N - 2][0] + D[N - 2][1] = S[N - 2]
 
    --> 점화식 : S[N] = S[N - 1] + S[N - 2]
    */
    for (int i = 2; i <= n; i++)
    {
        S[i] = S[i - 1] + S[i - 2];
    }
 
    cout << S[n];
 
    return 0;
}

 

바텀업이 더 효율적

 

 

TIP

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

 

이제 슬슬 패턴이 보이는 것 같다..?!

길이가 N인 이친수의 맨 끝자리가 0이 되려면, 앞에는 0, 1 모두 올 수 있다. 

길이가 N인 이친수의 맨 끝자리가 1이 되려면, 앞에는 0 만 올 수 있다.

 

길이가 N인 이친수의 끝자리가 k 인것을 D[N][k] 라 하자.

점화식으로 나타내면

 

D[N][0] = D[N - 1][0] + D[N - 1][1]

D[N][1] = D[N - 1][0]

 

그런데, 길이가 N -1 인 이친수의 끝자리가 0이려면 

그 앞자리에는 0 , 1 모두 와도 되므로

D[N][1] = D[N - 1][0] =D[N - 2][0] +D[N - 2][1] 

 

즉,

D[N][0] = D[N - 1][0] + D[N - 1][1]

D[N][1] = D[N - 2][0] +D[N - 2][1]

 

 

둘을 더하면

D[N][0] + D[N][1]

= D[N - 1][0] + D[N - 1][1] + D[N - 2][0] +D[N - 2][1]

 

 

이는 더 간단하게

D[N] = D[N - 1] + D[N - 2]   로 표현할 수 있다