-내 생각
우선 타일링 문제를 비롯하여 dp문제들은 기본적으로 점화식 세우는 것이 굉장히 어렵게 느껴진다... 다른 분들의 글을 보면 대다수가 점화식만 써놓은 경우가 많아 왜 저런 점화식이 세워졌는지 알 수 가없다.. 검색을 통해 알아보아도 점화식을 세우는 것은 그저 문제를 많이 풀어보는 수밖에 없다고 한다. ㅠㅠ
-해법
당연히 이 문제를 풀지 못해서 다른 분들의 글에서 도움을 얻었다. 문제 자체만으로도 점화식을 세우기 어려웠는데 예제 출력을 보면 알겠지만 웬 난생 처음보는 큰 숫자가 있다..
우선 점화식을 세워야 하는데, 이 문제의 경우 점화식을 세울 때 오른쪽이 막혔다고 생각하고 (오른쪽이 막힌 경우는 가로의 길이가 n인 경우이다.) n을 1씩 감소 시키면서 생각한다는 것이다. 즉, 가로가 n-1일 때, 2X1 크기의 타일을 한 개 설치 할 수 있다. 더 이상의 경우의 수는 없으므로 n-2를 고려해준다. n-2의 경우는 2X2 크기의 타일을 한 개, 2X1 크기의 타일을 눕혀서 2개를 만들 수 있다. (세워서 만드는 경우는 왜 안따지는지는 모르지만,) 2X1크기의 타일을 세워서 2개 설치할 경우는 이미 n-1의 경우에서 나왔던 모양이라 카운트하지 않는다고 한다. (여기서 카운트하지 않는다는 의미는 경우의 수로 고려하지 않는다는 의미이고 실제로는 3가지를 만들 수 있는 것이다.) 이후 n-3의 경우부터는 더 이상 새로운 모양이 등장하지 않으므로 dp [n] = dp [n-1] + 2 * dp [n-2]라는 점화식이 세워지게 된다. (n-1의 경우와 n-2의 경우로 모든 모양을 만들 수 있다.)
이제 점화식을 세웠으니, 구현을 해야 하는데, 예제 출력의 마지막 부분을 보면 터무니없이 큰 경우의 수가 존재한다는 것을 알 수 있다. 이렇게 몹시 큰 수는 BigInteger 클래스를 이용하면 저장이 가능하다고 한다. BigInteger클래스에 저장되는 수는 무한대? 또는 무한대에 가까운 큰 수까지 저장이 되기 때문에 dp배열을 BigInteger를 사용하여 선언하면 된다.
마지막으로 고려해야 할 부분은 n이 0일 때 이다. n의 범위가 0 <= n <=250이기 때문에 아무것도 설치하지 않는 경우도 존재한다는 것으로 해당 경우도 1개의 경우로 봐야 한다고 한다. 솔직히 이해 안간다. ㅋㅋㅋ 0! = 1인 개념이랑 유사하다는데 모르겠다..
import java.util.*;
import java.math.*;
public class Main {
static BigInteger dp[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
dp = new BigInteger[251]; // 0~250범위의 배열을 할당한다.
dp[0] = new BigInteger("1"); // 아무것도 설치하지 않는 경우의 수
dp[1] = new BigInteger("1"); // n이 1일 때 경우의 수
dp[2] = new BigInteger("3"); // n이 2일 때 경우의 수
for(int i=3;i<=250;i++) {
dp[i] = dp[i-2].multiply(new BigInteger("2")); // BigInteger는 일반적인 연산자를 사용할 수 없다고 한다.
dp[i] = dp[i].add(dp[i-1]); // 이러한 특수한 메소드를 사용하여 계산한다.
}
while(sc.hasNextInt()) { // 입력이 존재하면 계속 반복한다. , 테스트 케이스가 존재하지 않기 때문
int n=sc.nextInt(); // n이 들어오면
System.out.println(dp[n]); // 해당 n값을 출력한다.
}
}
}