백준 1904 01타일 [JAVA]

문제 해석

• 문제를 한마디로 요약하자면 0과 1만 사용할 수 있는 타일이 있고, 이 타일은 00를 1로 분해할 수 없다. 즉, 00과 1을 조합한 모든 경우의 수를 구하면 되는 문제이다.

• 아래는 N이 6일때까지 모든 경우의 수를 찾아낸 것인데 총 개수를 보면 규칙성이 보이는 것을 확인할 수 있다.

  

  • 1 -> 2(+1) -> 3(+1) -> 5(+2) -> 8(+3) -> 13(+5) => 피보나치 수열인 것을 확인할 수 있다.

코드

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

public class Main {

    static int[] fibonacci = new int[1000001]; //(1 ≤ N ≤ 1,000,000)
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        br.close();

        /*0과 1은 1이다. 2는 1+1 = 2 값 => 고정된 초기값*/
        fibonacci[0] = 1;
        fibonacci[1] = 1;
        fibonacci[2] = 2;

        //-1로 초기화 (구한 값인지 체크하기 위해)
        for(int i = 3; i < fibonacci.length; i++){
            fibonacci[i] = -1;
        }
        System.out.println(getFibonacci(N));

    }

    static int getFibonacci(int n){

        //구하지 않은 값이라면
        if(fibonacci[n] == -1){
            //어차피 증가폭은 같으므로 0~2까지 초기값 넣어주고 그 값들을 계속 더해주는 방향으로...
            fibonacci[n] = (getFibonacci(n-1) + getFibonacci(n-2)) % 15746;
        }

        return fibonacci[n];
    }
}

결과

느낀 점

• 피보나치 수열은 계속해서 나온 문제여서인지 큰 어려움없이 풀었다. (그리고 값들을 일일히 다 더해주지 않은 게 좀 다른 점이라면 다른점...?)