문제 출처

단계별로 풀어보기 > 동적 계획법1 > 01타일
https://www.acmicpc.net/problem/1904

문제 설명

1, 0 타일이 있다. 이 때, 0타일 2개가 붙어서 00타일이 되었다.
N개의 타일로 만들 수 있는 타일 종류의 수를 출력하라.
단, N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

접근 방법

예시를 N=5일 때까지, 만들다 보면 피보나치 수열과 동일한 양상을 띈다.
따라서 피보나치 수열과 같은 방식으로 풀이한다.
단, 항상 결과는 15746으로 나눈 나머지이므로, 저장할 때 이를 고려하여 저장한다.

import java.io.*;

public class O1타일 {

    public static int dp[];


    public static int fib(int n){


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

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

        dp[0] = 1;
        dp[1] = 1;

        int result = fib(N);

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

문제를 풀다보니 피보나치 수열과 같은 양상을 보여서 그렇게 풀었고, 설마 했는데 맞았다.
점화식을 이용하여 풀이하면 피보나치 수열과 같은 식이 나오기 때문이다.

마지막에 1이 붙는 경우는 앞에 길이 N-1짜리 문자열을 만들면 되므로 경우의 수는 dp[N-1] 이다.

마지막에 00이 붙는 경우는 앞에 길이 N-2짜리 문자열을 만들면 되므로 경우의 수는 dp[N-2] 이다.

따라서 dp[N] = dp[N-1] + dp[N-2]이다.

해당 코드의 시간 복잡도는 O(N)이다.

문제푼 흔적