백준 11726번 - 2xn 타일링 (Java 8)

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

11726번: 2×n 타일링

코드 :

dp, 탑다운

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

public class Main {
    static int[] tiles;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tiles = new int[n+1];
        tiles[0] = 1;
        tiles[1] = 1;
        //tiles[2] = 2; 선언 시 입력이 1일때 tiles 선언에서 인덱스 벗어남
        System.out.println(tile(n));

    }
    public static int tile(int n){
        if(tiles[n] != 0) {
            return tiles[n];
        }

        //미리 나눠야 저장되는 값이 바뀌지 않는다.
        tiles[n] = (tile(n-1) + tile(n-2)) % 10007;

        return tiles[n];
    }

방심하면 틀리게되는 문제 같다. 직사각형을 그려보다보면, 피보나치 수열처럼 규칙이 성립하는 걸 알 수 있다.

참고 :

pro hyeon님 블로그

이분은 탑다운 바텀업 두 방법으로 모두 풀어보셨다. 그림도 친절하게 색깔을 구분해서 그려서 알아보기 쉬웠다.