처음 보자마자 피보나치처럼 재귀로 풀면 쉬울 것 같다고 생각했다. 그래서 top-down 방식으로 재귀함수를 구현해서 풀었다. 어우 시간초과가 났다. 솔직히 날 이유가 없어보였다. 시간복잡도도 O(n) 이었기 때문이다. 그래서 다음 방법으로 dfs를 사용했다. 이번엔 bottom-up 방식으로 했다. 또 시간초과가 났다. 근데 이건 생각해보니 방문했던 곳을 계속해서 방문하기 때문에 시간초과가 날만했다. 두 번의 좌절 끝에 질문 게시판에 들어가봤는데 나하고 같은 고민을 하셨던 분이 계셨다. 알고보니 소요 시간이 0이 가능했던 것이다. 그래서 dp배열을 0으로 초기화하면 재귀함수로 구현해도 dfs와 마찬가지로 방문했던 곳을 계속해서 방문할 여지가 있었다. dp배열을 -1로 초기화했더니 맞았다. 코드는 간단하..

이항 계수 1 문제와 다른 점은 n과 k의 범위가 더 커졌다는 것이다. 그래서 그냥 변수를 double형으로 바꿔주고 계산 중간마다 %10007 연산을 해주면 될 줄 알았다. 그런데 이 방법이 잘 먹히지 않았다. 그래서 알고리즘 분류를 한 번 봤는데 DP가 딱 있는 것이다. 바로 2차원 배열을 만들어주자. (근데 DP말고 분할정복으로는 못푸나? 한 번 시도해봐야겠다.) arr[i][j]는 iCj 를 의미한다. k=0일 때, 즉 nC0=1이므로 처음에 따로 예외로 처리했는데 그냥 arr에 표현해도 똑같았을 것 같다. 그런데 나중에 나올 nCr = n-1Cr + n-1Cr-1 에서 r=0이 되는 경우는 없기 때문에 따로 예외처리했다. 모두가 알고 있듯 nCn=1이고 nC1=n 이다. 이를 배열에 저장해주었다..