본문 바로가기

파스칼의 삼각형1

프로젝트 오일러 #53 : 조합 선택 이번 문제는 간단한 문제입니다. 조합 공식만 알면 쉽게 문제를 풀 수 있습니다.  n이 1부터 100까지 변할 때, 조합 숫자 nCr을 계산할 때, 1백만이 넘는 결과가 나오는 갯수를 적으면 됩니다.단순무식한 방법으로 하더라도, 총 10,100 번 조합 계산을 하면 됩니다. nCr=nCn−r이라는 사실을 알고 있다면, 그 절반으로 줄테고요. 대칭형인데, 단순증가 단순감소 패턴이라는 것을 아신다면, 더 횟수를 줄일 수 있습니다. 단, 조합을 계산하는 곱하기 횟수가 증가하니, 실제 곱하기 횟수로 따진다면, O(n3)정도의 시간 복잡도를 가집니다. n이 100정도이니, 시간이 아주 조금 더 걸리는 것 뿐이지, 계산 못 할 정도는 절대 아닙니다. 저는, 조금 특이한 방법.. 2016. 6. 9.
728x90

티스토리툴바