백준 13430번 합 구하기
2021.05.24
문제 S는 다음과 같이 정의된다. S(0, n) = n (모든 양의 정수 n) S(k, n) = S(k-1, 1) + S(k-1, 2) + ... + S(k-1, n) (모든 양의 정수 k, n) k와 n이 주어졌을 때, S(k, n)을 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 풀이 이 문제같은 경우 어떤 성질을 이용해 점화식을 도출하고 ... 라는 일련의 과정보단, 직접 써보는 것이 이해가 빠를 것이다. 직접 써보니 이런 식의 표가 나왔다. 실제로 문제의 수식대로 저기까지만 계산해도 상당히 머리아픈데, 사람은 귀찮은걸 싫어하다보니.. 저거 쓰는 과정에서도 수를 빨리 도출해내는 법을 찾게 된다. 쓰다 보면 금방 찾는 규칙인데, 규칙은 다음과 같다. 파란색 원 안의 수는 그 ..