[BOJ] 01타일_1904

 

이 문제의 유형은 타일과 같은 여러 문제들에서 비슷하게 응용된다.

이 문제의 핵심은 다음과 같다.

 

 

그림을 예로 보았을 때, dp[4]를 구하는 방법을 생각해보겠다.

dp[2]는 타일이 두개일 때, 구할 수 있는 모든 경우의 수이다.

만약 여기에 00타일 두개가 들어가고, dp[3]에는 1타일 한개가 들어간다면

4개짜리의 모든 경우의 수가 나온다.

 

하지만 난 여기서 뭔가 거슬리는 생각들이 있었다.

dp[2]에 00을 추가할 때, 순서를 바꿔준다면 다른 경우가 되지 않을까?? 그리고 두개를 추가한다고 했을 때, 00말고 11을 넣는다면,,?

 

물론 잘못된 생각이지만, 한번은 짚고 넘어가자.

저 생각은 왜 잘못된 것일까?

 

이 잘못된 생각의 흐름은 어디서 부터 시작된걸까?

일단 dp[2]의 11에 00을 앞뒤로 붙는다고 생각했었다.

1100, 0011...뭐여? 00만 추가했는데 1100, 0011, 0000 이렇게 세 가지가 나오잖아?! 그럼 dp[2]에 00을 추가하는 방법의 생각은 틀린건가?!

 

다른 블로그들도 찾아보고 여러 풀이들을 보았지만, 명확한 해답은 보이지 않았다.

다만 조금 더 이해할 수 있게 설명하자면, 00 or 1의 타일을 추가할 때 한 방향으로만 추가를 해야한다는 것이다.

그렇지 않다면, 중복된 값이 나오기 떄문이다.

ex) 1001(001에 앞에 추가) 1001(100에 뒤에 추가)

 

따라서 이러한 사고과정으로 점화식 a[n] = a[n-2]+a[n-1]이라는 값이 나오게 된다.

 

아 그리고 또 주의할 것이 있다.

바로 n=1일 때이다.

코드로 작성했을 때, 이것을 고려하지 않으면 런타임 index Error가 나오게 된다.

그것은 n=1일 때를 고려하지 않고, dp[2] = 2라고 초기화를 하기 떄문에 발생하는 경우이다.