백준(BOJ) 1904: 01타일

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

무조건 "나는 답을 모른다. 하지만 정답은 어찌됐든 최적의 원리가 적용되어 최적해는 부분해를 이용하여 이미 정의되어 있다"는 것을 기억하고 최적해를 부분해로 정의하기 위해 관계를 찾기 위해 그림도 그리고 그림간의 관계를 살피기 위해 시간을 써야 한다는 것이다. 

일종의 영감은 어찌 됐든 그 후다. 이 문제에서 영감이라 함은 0두개가 붙어있으므로 길이가 2인 "00" 타일하나와 길이가 1인 "1"타일 하나, 총 2종류의 타일만이 존재한다는 것이다. 이는 곧 An은 An-1에서 앞에 "1"블럭 하나를 더한 경우와 An-2에서 앞에 "00"블럭 하나를 더한 An=An-1+An-2와 같은 점화식을 생각할 수 있게구나 하는 생각으로 이어진다. 

DP문제를 해결하는데 있어서 나만의 점화식을 세우는 것이니 그 안에서는 내가 규칙을 만들고 그것을 철저히 지키면서 점화식을 세우는 것이 필요하다. 이 말이 무슨 말이냐 하면 아래와 같은 그림에서 An-1, An-2각각에 1혹은 00을 붙여가면서 규칙을 찾아가고 있는데 뜬금없이 An-1에서 1은 앞에다가 붙이고 An-2에서 00은 뒤에다가 붙인다. 라는 식으로 규칙을 파괴해가며 찾는것은 해선 안된다는 것이다. 

마지막으로 왜 An-2의 경우경우에 앞에 00은 붙여주지만 11은 붙여주는 경우를 생략하는가? 라고 생각할 수 있다. 그 이유는 점화식이 An=An-1+An-2로 구성되기 때문에 이미 그간 차곡차곡 쌓아온과정에서 앞에 11이 붙는 경우는 An-1이 카운팅하면서 왔기 때문이다. 

---------------------------------------------------------------------------한번생각해보기-----------------------------------------------------------------

그런데 다시 생각해보니 이 점화식은 피보나치 점화식이다. 즉, 피보나치 수열의 의미가 어떤것인지 다시금 생각해 볼수 있게 한다. An은 An-1에서 특정수(1)를 더하고 An-2에서 특정수(00)를 더한경우의 합이다.

그렇다면 서로 구분되는 특정수를 생각할 수 있다면 An=An-1+An-2+An-3 과 같은 식으로도 표현되어 질수 있을까? 그건 아직은 잘 모르겠다. 세상에 널린것이 문제니 다른 문제 맞딱뜨린다면 생각해 보자.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;

public class Testing3 {
    public static void solution(int n) {
        if (n <= 2) {
            System.out.println(n);
            return;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; ++i)
            dp[i] = (dp[i - 1] + dp[i - 2])%15746;
        System.out.println(dp[n]);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        solution(n);
    }
}