[백준]2407번 조합

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

2407번: 조합

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

---

nCm = n-1Cm-1 + n-1Cm을 활용할 수 있다. 하지만 이 식을 long long으로 한다면 overflow가 나버리기 때문에 string으로 하여 연산을 하여야 한다.

string으로 된 배열 두 개를 더할 때 뒷자리 숫자부터 더해야 하는데 더한 숫자가 9보다 크다면 10을 뺀 후 carry를 1로 설정하여 다음 자릿수를 더할 때 활용해야 한다.

 

---

처음에 int로 했을 때 안될 것 같아서 long long을 사용하였는데도 안되었다. 생각보다 조합의 숫자가 컸던 것이다. 그래서 string으로 하겠다는 생각을 하였고 코드를 작성하였지만 내 생각과 동일하게 코드를 작성하는 것이 힘들었다. 작은 숫자와 큰 숫자, carry의 존재 char로 숫자를 표현하는 방법 등 42서울에서 많이 했던 것인데 꽤나 고생을 하였다. 처음에 난이도를 보고 얕잡아 봐서 구상을 제대로 안했던 것이 흠이었던 것 같다.