[Silver V][JAVA] 1904번:01타일

🔗 링크
https://www.acmicpc.net/problem/1904

📖 문제

📕풀이 방법
Dynamic Programming 은 특성상 2가지의 방법으로 해결할 수 있다.
Top Down
Bottom Up[✅]

점화식

arr[i] = (arr[i - 1] + arr[i - 2])

문제요약

00과 1로 만들 수 있는 2진 수열의 개수를 구하시오.

수열을 만들기 위해서 주어지는 수가 2가지(1, 00) 종류이다.

풀이

길이가 n인 수열을 여러개 만들어서 규칙을 찾아보자.
피보나치 수열로 풀 수 있다.

N=1일 때, [1] - 1개
N=2일 때, [00, 11] - 2개
N=3일 때, [001, 100, 111] - 3개
N=4일 때, [0000, 0011, 1001, 1100, 1111] - 5개
N=5일 때, [00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111] - 8개

마지막 조건이 하나가 더 추가된다.
15746을 나눈 나머지를 출력하라고 했다.

코드

package baekjoon_java.SilverIII;

import java.io.*;

public class 공일타일 {//1904번 01타일
    private static final int MOD = 15746;
    static int arr[] = new int[1000001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;

        System.out.print(DP(N));
    }

    // Bottom-Up
    private static int DP(int N) {
        for (int i = 3; i <= N; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;
        }

        return arr[N];
    }
}