[백준 1905, Java] 01타일

문제

www.acmicpc.net/problem/1904

1904번: 01타일

 

풀이

  전형적인 dp문제다. 이 문제의 점화식 f(n)을 00,1로 만들 수 있는 크기가 n인 2진수열의 경우의 수라고 하면 f(n) = f(n-1) + f(n-1)가 된다. f(n) 의 경우에 해당하는 수열의 마지막에는 00 또는 1이 올 수 있다. 00이 오게되는 경우 앞에는 n-2자리의 2진수열이 오게되고, 1 이 오는 경우에는 앞에 n-1 자리의 2진 수열이 온다. 따라서 f(n) 은 위의 두가지 경우를 합친 f(n-2) + f(n-1)이 된다.

 

 

코드

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

public class Main {
    public static long[] memo;
    public static int N;
    public static int MOD = 15746;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        memo = new long[N+1];

        long result = bottomUp(N);
        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();

    }
    public static long topDown(int n){
        if(n<=2){
            memo[n] = n;
            return memo[n];
        }
        else if(memo[n]>0){
            return memo[n];
        }
        else{
            memo[n] = topDown(n-1) + topDown(n-2);
            memo[n] %= MOD;
            return memo[n];
        }
    }

    public static  long bottomUp(int n){
        for(int index = 1; index<=n ; index++){
            if(index<=2){
                memo[index] = index;
            }
            else{
                memo[index] = (memo[index-1] + memo[index-2])%MOD;
            }
        }

        return memo[n];
    }
}