[Week 4] TILING2 self review - Scaachan

[Queue-ri]

TILING2 self review

• 파일명: TILING2/Scaachan.cpp
• 수행시간: 0ms

1. 문제 해결 과정

nCr 규칙을 발견하긴 했으나 문제가 간단하여 dp로도 나쁘지 않은 수행시간이 나올 것 같았습니다.

2 * 1 크기의 타일을 가로로 놓으면 같은 열의 빈 공간은 똑같이 가로로 놓을 수 밖에 없으므로,

로직을 단순화하여 1을 놓을 것인지 2를 놓을것인지의 문제로 축소합니다.

2. 아이디어

dp로 풀었습니다.

3. 코드 설명

https://github.com/Scaachan/Advanced-Algorithm-Study/blob/0eeec5a3adfb004dbd384dc69cb9a5d3044528aa/TILING2/Scaachan.cpp#L11-L20
처음 제출할 때 한 번 틀렸는데 base case 검사를 메모이제이션 확인 이후에 하는 습관이 원인이었습니다.

제 코드에선 메모이제이션 검사가 우선이기에, out of index 를 방지하기 위해 배열 크기를 100이 아닌 102로 잡아주어야 합니다.

로직은 PI 문제 풀이와 상당히 유사합니다. 1 또는 2로 쪼개었을 때 N과 일치하면 딱 맞게 쪼갠 것이니 1을 return 하고,

N을 초과하면 잘못 쪼갠 것이므로 0을 return 합니다.

마지막으로, 경우의 수가 크니 arithmetic overflow를 방지하기 위해 return 값에 mod P 를 한번 적용해줍니다.