[알고리즘-JAVA] 백준 알고리즘 2193번 - 이친수

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

n자리 이친수의 총 개수를 구하는 문제이다.

 

2. 나의 방식대로 문제를 재정의 하자.

d[n] = n자리 이친수의 총 개수라고 하고 dp를 이용해 푼다.

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

재귀함수 (Top-down)이나 반복문(Bottom-UP)을 사용할 계획이다.

4. 어떻게 계산할 것인가?
1) 입력

BufferedReader를 사용해 입력받을 것이다.

 

2) 시간 복잡도 계산

d[n] 한칸을 채우는데 = O(N)

 

5. 주의할 점은 무엇인가?

N이 90까지라서 int 범위가 모자랄 수 있다.

 

6. 풀이 과정

2진수이기 때문에, n자리에 올 수 있는 수는 0과 1 두가지이다.

1) n자리에 오는 수가 0일때 

..... 0 or 1 , 0

    (n-1)    (n)

n번째 자리에 0이 들어왔으므로 앞에는 0혹은 1 둘다 올 수 있다. (연속하는 11이 없기 때문에)

따라서 맨 끝에 0이오는 경우는 d[n-1]이다.

2) n자리에 오는 수가 1일때

..... 0or1,  0,  1

    (n-2)(n-1)(n)

n번째 자리에 1이 들어왔으므로 앞에는 0밖에 올수가 없다. (연속하는 11을 만들기 때문에)

따라서 n-1번째 자리가 0이므로 n-2번째 자리는 0 혹은 1이 올 수 있다.

따라서 맨 끝에 1이 오는 경우는 d[n-2]이다

 

따라서!

점화식 : d[n] = d[n-1] + d[n-2]을 만족시킨다.

 

Bottom-UP 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String args[]) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int count = Integer.parseInt(br.readLine());
            long d[] = new long[count+1];
            // d[n] = n자리 이친수.
            d[0] = 0;
            d[1] = 1;
            for (int i = 2; i <= count; i++){
                d[i] = d[i-1] + d[i-2];
            }
            System.out.println(d[count]);
    }
}

Top-Down 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static long d[];
    public static void main(String args[]) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int count = Integer.parseInt(br.readLine());
            d = new long[count+1];
            System.out.println(Calculate(count));
    }

    public static long Calculate(int count){
        if(count == 0){
            return 0;
        }
        if(count == 1){
            return 1;
        }
        if(d[count] > 0){
            return d[count];
        }
        d[count] = Calculate(count-1) + Calculate(count-2);
        return d[count];
    }
}