[백준/JAVA] 1904: 01타일

[백준/JAVA] 1904: 01타일

크기가 n인 2진 수열을 만드는데, 0은 무조건 짝수개씩만 붙어있을 수 있다. n일때의 2진 수열의 경우의 수를 구하고 이를 15746으로 나눈 나머지를 출력해야 한다.

뜬금없이 15746으로 나누는 이유는 무엇인가 했는데, n이 너무 커지는 경우에 값이 과하게 커지는 것을 방지하기 위해서인 것 같다.

처음에는 수열의 경우의 수를 세야 하나 막막해했는데, 저번에 비슷한 문제를 풀었던 것이 떠올랐다. n=1부터 값을 대입하여 하나하나 세어보면 해당 문제는 피보나치 수열로 풀어진다는 것을 알 수 있다.

$f[1]=1\,(1)$
$f[2]=2\,(11,00)$
$f[3]=1+2=3\,(111,100,001)$
$f[4]=2+3=5\,(0011, 0000, 1001, 1100, 1111)$
$...$

이후의 값은 이전 값에

1. "1"을 붙이거나
2. "00"을 붙이는

2가지의 경우의 수가 존재한다.

예를 들어 N = 3일 때는 N - 1번째, 즉 $f[2]$의 값에 "1"을 붙이거나, N - 2번째 $f[1]$의 값에 "00"을 붙여 크기가 3인 2진 수열을 만들 수 있다. 따라서 N - 1번째의 경우의 수와 N - 2번째의 경우의 수를 합한 것이 $f[n]$으로 나타난다.

이전 값에 숫자를 붙여 이진 수열로 만듬으로써 결국엔 N = 3부터 피보나치 수열의 형태를 나타내게 되는 것이다.

단순히 재귀함수로 풀면 시간초과가 날 것 같아 bottom-up 방식의 동적 프로그래밍 기법을 사용하였다. ($f[i]$를 구할 때 $f[i-1]$과 $f[i-2]$는 이미 구해져 있기 때문에 시간이 훨씬 단축된다.)

소스코드

---

import java.io.*;

public class Main {
	public static long f[];
	public static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        f = new long[n+2];
        System.out.println(fib(n));
    }
    
    // 2진 수열을 만드는데, 0은 홀수개 있을 수 없고 짝수개씩 붙어있을수만 있다.
    // 길이가 n인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
    // 결과를 보면 f=3부터 피보나치 수열로 나타난다는 것을 알 수 있다.
    public static long fib(int n) {
    	f[1] = 1; // 1
    	f[2] = 2; // 11, 00
    	for (int i=3; i<=n; i++)
    		f[i] = (f[i-1] + f[i-2])%15746;
    	return f[n];
    }
}