[백준 baekjoon] 1904번 01타일 (동적 계획법 dp) 자바 Java 풀이

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

풀이

1. 백트랙킹

import java.io.*;
import java.util.*;

class Main {

    public static int[] arr;
    public static int count = 0;


    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());

        arr = new int[N];

        dfs(0, N);
        bw.write(String.valueOf(count % 15746));
        bw.flush();
        bw.close();
    }


    public static void dfs(int depth, int N) {

        if (depth == N) {
            for (int i : arr) {
                System.out.print(i + " ");
            }
            count++;
            System.out.println();
            return;
        }

        if (depth <= N - 2) {
            arr[depth] = 0;
            arr[depth + 1] = 0;
            dfs(depth + 2, N);
        }

        arr[depth] = 1;
        dfs(depth + 1, N);


    }


}

• 작은 수는 잘 출력되지만 큰 수를 입력하면 시간이 매우 오래 걸린다. 시간 초과가 났다.
• N 크기의 arr 배열을 생성하여 depth에 해당하는 index를 두 가지 경우로 나누어 채웠다.
• 만약 depth가 N-2보다 작거나 같다면 뒤에 00을 이어 붙일 수 있는 경우이므로 arr 배열의 depth와 depth+1 인덱스를 0으로 채워준다. 이후 dfs 호출에 depth는 2를 증가시킨다.
• 1을 어느 경우에나 올 수 있으므로 따로 조건을 주지 않고 arr 배열의 depth 인덱스를 1로 채워준다. 이후 dfs 호출에 depth는 1 증가시킨다.

2. 동적계획법

• 위의 코드를 통해 1~10까지를 구해보며 피보나치 수열과 동일한 결과가 나옴을 알 수 있었다.

1 -> 1
2 -> 2 
3 -> 3
4 -> 5
5 -> 8
6 -> 13
7 -> 21
8 -> 34

import java.io.*;
import java.util.*;

class Main {

    public static int[] dp;


    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(dfs(N)));
        bw.flush();
        bw.close();
    }


    public static int dfs(int N) {

        dp = new int[N];

        if (N == 1) return 1;
        if (N == 2) return 2;


        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < N; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        }

        return dp[N - 1];

    }


}

• N이 1이거나 2일 때는 먼저 값을 반환한다. dp 배열의 인덱스 0, 1의 값을 채울 때 에러가 나지 않게 하기 위함이다.
• dp[0]과 dp[1]의 값을 각각 1과 2로 채워준다.
• 2부터 N까지 루프를 돌며 계산해준다.
• 15746으로 나누는 부분에 주의해야 한다. 마지막에 나눠주게 되면 이미 정수 값을 초과하여 이상한 값이 출력될 수 있다. dp 배열에 값을 저장할 때마다 15746으로 나눠주어야 모든 수열의 값이 정상적으로 들어간다.