백준 2407 - 조합(C++)
문제 nCm을 출력해라. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤100, m ≤ n) 예제 입력 100 6 예제 출력 1192052400 문제 해결 어디서 힌트를 얻을 수 있을까? 'nCm'과 '조합'이라는 키워드를 보았을 때 나는 이항 계수를 떠올렸다. 그리고 수많은 반복되는 중복 문제를 고려하여 다이나믹 프로그래밍도 적용도 생각했다. 그리고 최대 범위의 조합의 수를 고려하면 커다란 범위의 수를 어떻게 처리해야 할 지도 고안해야 했다. 우선 하나하나 해결해보도록 해보자. 우선 이항 계수를 삼각형으로 표현한 파스칼의 삼각형의 점화식을 보도록 하겠다. 위의 점화식에 따라 커다란 틀을 구현할 수 있겠다. 그리고 메모이제이션은 다음과 같이 할 수 있다. (N, M)쌍에 값이 이미 갱신..
알고리즘/문제
2023. 5. 26. 00:29
