반응형 약수의 갯수 구하기1 12. 프로젝트 오일러 #12 : 500개 초과 삼각수 구하기 이번 문제는 삼각수에 대한 것입니다. 간단한 중학수학 수준만 알고 있다면, 이 문제를 좀 빠르게 풀 수 있을 것이라 생각합니다. 1~n 까지의 합은 다음과 같은 식으로 구할 수 있습니다. 그 다음은 약수들의 갯수를 구하는 방법입니다. 예를 들어서 12의 약수의 갯수는 다음과 같이 계산할 수 있습니다. 이것만 알아도, 보다 쉽게 약수의 갯수를 구할 수 있습니다. 조금 더 나아간다면, n과 n+1은 서로소관계이므로, 을 적용할 수 있습니다. 그래서 n이 짝수인 경우와 홀수인 경우로 나누고, 동적 프로그래밍을 이용하면, 빠르게 원하는 답을 얻을 수 있습니다. 프로젝트 오일러 사이트에 가보면, 어떤분은 수십초가 걸렸다고 하는데요. 제 경우에는 노트북에 가상머신을 잡고 리눅스를 돌렸는데, time으로 실행시간을 .. 2014. 12. 29. 이전 1 다음 728x90