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