https://programmers.co.kr/learn/courses/30/lessons/12902
-
intro
이제부터 level 4로 진입하게 되었다.. -
flow
이제 슬슬 이런 문제가 보이면 또 점화식이 있겠구나라는 생각이 먼저 든다. 제한 조건이 정확하지 않은데 일단 n은 짝수만 허용하는 것이라 단정 지었다. 홀수는 타일로 구성하기 불가능하기 때문에.. 어쨌든 뭔가 f(n+2) 와 f(n) 간의 관계를 찾아야 할 것 같다. 일단 간단히 생각해보면 f(2) 는 3이다. n+2 가 됐을 때, 추가된 2만큼 가로의 길이에서 나올 수 있는 경우의 수는 3가지 (가,세세), (가,가,가), (세세,가) 그러면 이러한 관계에서의 점화식은 f(n+2) = 3xf(n) 이 일부분을 표현해준다고 생각할 수 있다. 이 점화식 상에서 표현이 안되는 예외 케이스 들을 찾아 보니, 홀수 부분에 가로타일이 걸쳐져 있는 경우이다. 무슨 뜻이냐면 n과 n+1의 경계를 넘어서 가로 타일이 놓이는 경우이다.. 이러면 단순히 f(n)만으로 f(n+2) 을 표현할 수 없게 된다. 그래서 f(n-2) 까지 생각의 범위에 넣어 보았다. 홀수 부분에 예외케이스가 발생하려면 어떤 상황이어야 되나 봤더니 n번 째 타일 중 최소 하나는 세로로 놓여져 있어야 한다는 것을 발견했다. 그렇다면 n-2 ~ n 사이의 타일들이 모두 가로로 놓이는 경우는 예외 부분에 가로 타일이 들어갈 수 없게 된다. 이런 경우의 수는 f(n-2) 와 같다. 거기다 예외 케이스가 발생할 때도 가능한 상황별로 각각 1가지씩 추가 되는 것 밖에 경우의 수가 존재하지 않으므로 예외를 처리하는 공식은 f(n)-f(n-2) 로 처리가 가능하게 된다.
결론은 f(n+2) = 3xf(n) + f(n) - f(n-2) 가 된다.
지금 보니 4xf(n) - f(n-2) 로 표현이 가능하다.
이런 dp로 풀면 시간복잡도는 당연히 O(N) -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A1.py
