[알고리즘] 백준 '이항 쇼다운'

https://www.acmicpc.net/problem/6591

정답 비율이 낮아서 겁먹고 미뤘던 문제입니다.

그런데 다른 쉬웠던 이항 계수 문제랑 거의 똑같이 했는데도 패스가 나네요.

무엇??

그냥 캐시를 사용한 동적계획법으로 풀었더니 시간, 공간 복잡도가 안습이긴 하지만 패스는 되더라고요.

이후에 검색해서 공부한 방법으로 다시 풀었더니 정석대로 패스된 것 같습니다.

동적계획법으로 풀때의 아이디어는 위키백과에서 봤던 C(n, r) = C(n, n-r)이라는 점을 이용해서 중복 계산을 피하는 것이고

r = 0, r = 1, n = r일때는 답이 명확하므로 조건문을 써줬다는 것?

캐시는 최대한 크게 할당하고 n, r이 범위에 있을때만 캐시를 검사하도록 했습니다.

2번의 메모리 초과는 적절한 캐시 크기를 찾는다고 ㅋㅋ...

정석으로 풀때의 아이디어도 C(n, r) = C(n, n-r)이라는 점을 이용하고 팩토리얼이 들어간 이항 계수 공식에서 약분을 이용해 계산을 줄이고 오버플로를 피했다는 것이네요.