배경

코딩 테스트를 복습하는 시간을 갖도록 하겠습니다.
문제는 산 모양 타일링입니다.

본론

반성

문제를 스스로 풀지 못하고, 카카오 공식 문제 해설를 참조하였습니다.
약 8시간 정도 고민을 해봤지만, 명확한 풀이를 찾지 못했습니다.
- DP 유형임을 파악했지만, O(N) 성능을 보장하는 규칙성을 찾지 못했습니다.
- 저는 사다리꼴 윗변이 i일 때, 마름모 개수 j를 사용했을 때 경우의 수를 점화식으로 표현하였습니다.
  - arr[i][j] = k*arr[i-1][j-1] - arr[i-2][j-2]
    - arr[i][0] = 1
    - k = tops[i] ==1 ? 3 : 2;
  - 간단히 표현하져면, i,j에 대한 경우의수 = (새로운 마름모를 둘 수 있는 경우의수) * (i-1,j-1에 대한 경우의수) - (새로운 마름모가 겹칠 때 경우의수)
- 이러한 방식은 O(N^2) 성능이므로, n<=10^5인 상황에서 적합하지 않았습니다.
제가 생각한 실수는 다음과 같습니다.
1. 실패를 인정할 줄 알아야했습니다.
  - 공식 답안 아이디어는 그 당시에 제가 절대 생각하지 못할 아이디어였습니다.
  - 처음에 떠올린 방법에 너무 매몰되어 시야가 좁아지기도 했습니다.
2. dp 문제를 소홀히 공부하였다.
  - 해당 문제는 아이디어만 떠올리면, 누구나 쉽게 풀 수 있는 문제였습니다.
  - DP 알고리즘 유형에 익숙하지 않음을 깨닫을 수 있었습니다.
해당 문제에 키 포인트는 다음과 같다고 생각합니다.
1. 기준점을 찾을 수 있는가?
- 타일 개수 증가시 반드시 가운데 역삼각형 모양이 추가됩니다.
- 타일의 맨 윗부분은 가운데 역삼각형과 접합니다.
- 모든 마름모 모양은, 가운데 역삼각형을 만드시 포함합니다.
  따라서, 기준점은 역삼각형으로 표현할 수 있습니다.
1. 기준점 i와 i-1의 경우의 수 관계를 구할 수 있는가?
- 마름모 회전은 12시,7시,5시 방향이 가능합니다.
- 기준점 i-1의 마름모 위치는 기준점 i의 경우의 수에 결과를 미칩니다.
  - i-1의 마름모가 5시 방향에 위치하면, i의 마름모 위치는 7시에 위치할 수 없습니다.
  - i-1의 마름모가 그외 방향에 위치하면, i의 마름모 위치는 모든 방향에 위치할 수 있습니다.
    따라서, i의 경우의수는 i-1의 마름모가 5시에 있을 때 경우의 수와 i-1의 마름모가 5시에 있지 않을때 각각 2가지 상황을 고려해야합니다.