BOJ) 01타일

01타일

1904번: 01타일

풀이

 

처음 문제를 봤을 때는 순서를 모두 구해주어야 한다고 생각했다.

그래서 처음 로직은 for문을 돌리면서 0타일이 n이하까지 2개씩 증가시키면서, 1타일은 n-0타일의 수 를 통해 각각 타일의 수를 구해주었다.

그리고 0타일은 2개를 1개로 인식해야하기 때문에, /2를 해주었다.

 

0타일의 갯수 : ZERO

1타일의 갯수 : ONE

total = ZERO + ONE

 

위의 변수를 가지고 따지면, total! / ZERO! / ONE!    ( ! = 팩토리얼)

이라는 식을 세웠다.

하지만, 최대 n이 1,000,000이나 되기 때문에 팩토리얼은 쓸 수 없다고 생각했다.

 

그러다가 문제를 자세히 보니까, 1 ~ 6까지 피보나치의 형태를 띈다는 것을 발견했다.

그래서, 싹 다 갈아엎고 피보나치로 풀었다..

 

결론 = 피보나치

 

코드

 

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

public class Tile01_1904 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        solution(n);
        br.close();
    }

    private static void solution(int n) {   // fibonacci...
        if(n <=3) {
            System.out.println(n);
        } else {
            int left=1,right=2,now=3;
            final int mod = 15746;
            for(int i=4; i<=n; i++) {
                left = right;
                right = now;
                now = (left+right)%mod;
            }
            System.out.println(now);
        }
    }
}