[BOJ] 백준 1904 - 01타일 풀이

1. 문제

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

1904번: 01타일

 

2. 풀이

백준 알고리즘 분류에 다이나믹 프로그래밍(DP)로 분류되어 있는 문제이다. 이 문제에서는 N이라는 크기가 주어질 때 "00" 타일과 "1" 타일로 만들 수 있는 경우의 수를 구하는 문제이므로 dp[N] = 만들 수 있는 경우의 수로 설정했다.

(1) N = 1
- "00"은 최소 크기가 2이므로 사용할 수 없고 "1" 하나만 사용할 수 있다. 
- dp[1] = 1

(2) N = 2
- "00", "11"을 만들 수 있다. 문제에 나와 있듯이 "01"과 "10"은 만들 수 없다.
- dp[2] = 2

(3) N = 3
- "001", "100", "111"을 만들 수 있다.
- dp[3] = 3

(4) N = 4
- "0000", "1111", "0011", "1100", "1001"을 만들 수 있다.
- dp[4] = 5

(5) N = 5
- "00001", "10000", "00100", "11100", "11001", "10011", "00111", "11111"을 만들 수 있다.
- dp[5] = 8

(6) N = 6
- "000000", "100001", "000011", "001100", "100100", "110000", "001111", "100111", "110011", "111001", "111100", "111111"을 만들 수 있다.
- dp[6] = 13


dp[3]을 보면 하나 전과 두개 전을 더했을 때의 값과 동일하다. (dp[3] = d[2] + dp[1])
dp[4]와 dp[5], dp[6]도 마찬가지다.
따라서 이는 피보나치 수열을 가진다는 것을 알 수 있다.

N을 입력 받아서 N이 1과 2일 때만 따로 출력을 해주고 N >= 3일 때 메모이제이션을 통해 저장한 값을 더해준다.
단 문제에서 15746으로 나눈 나머지를 출력하라고 했는데, 마지막 결과에서 나누어주면 틀린 값이 되므로 피보나치 수열 반복문을 실행할 때마다 나누어주어야 한다.

3. 소스 코드

import java.io.*;

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());
        int[] dp = new int[N + 1];

        if (N == 1) {
            bw.write("1");
            bw.flush();
            bw.close();
            br.close();
        } else if (N == 2) {
            bw.write("2");
            bw.flush();
            bw.close();
            br.close();
        } else {
            dp[1] = 1;
            dp[2] = 2;

            for (int i = 3; i <= N; i++) {
                dp[i] = (dp[i - 2] + dp[i - 1]) % 15746;
            }
            bw.write(Integer.toString(dp[N]));
            bw.flush();
            bw.close();
            br.close();
        }
    }
}