[백준] 1904 01타일 - Dynamic Programming / Java

• 문제 링크

1904번: 01타일

 

• 풀이 과정

크기가 n 인 타일링의 가짓수를 구해보면,

 

n = 1	(1)	1개
n = 2	(00), (11)	2개
n = 3	(001), (100), (111)	3개
n = 4	(0011), (1100), (1001), (0000), (1111)	5개
n = 5	(00001), (10000), (00100), (00111), (11100), (10011), (11001), (11111)	8개

위와 같이 가짓수의 증가폭이  1, 2, 3, 5, 8 로 피보나치 수열과 같다.

이에 대한 점화식 dp[i] = dp[i - 2] + dp[i - 1] 을 적용해

크기가 n인 타일링의 가짓수 dp[n] 을 정답으로써 출력하며, 만약 n = 1 이라면 1을 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        bw.write(String.valueOf(tiling(n)));
        bw.flush();
    }

    private static long tiling(int n) {
        if (n == 1)
            return 1;

        long[] dp = new long[n + 1];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i - 2] + dp[i - 1]) % 15746;

        return dp[n];
    }

}