[BOJ] 2407 조합 (C/C++)

2407번: 조합

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

---

문제가 참 심플하다. 널리 알려져 있는 다음과 같은 점화식을 사용해서 쉽게 풀 수 있을 줄 알았다. 점화식이 이미 들통한 DP 문제만큼 쉬운 문제는 없다. 메모이제이션 + DP를 사용하면 간단하게 풀린다. 하지만 숫자가 너무 커서 이걸 문자열로 계산해야 하는 문제였다. 

 

$$ \binom{n-1}{m-1} + \binom {n-1}{m} = \binom{n}{m} $$

 

문자열로 계산을 하다보니 그냥 출력하면 거꾸로 나온다. 그래서 출력을 뒤집어야 한다.

 

후기)

문제가 그리 어렵지는 않았다. 하지만 수식을 문자열로 계산하는걸 진짜 오랜만에 해본 것 같다. 아마 1학년 때 기초 코딩 과목을 들으면서 였겠지...? 오랜만이라 감회가 새로웠다.