31. 프로젝트 오일러 #31 : 코인들의 합
이번문제는 재귀 함수를 만들어서 프로그램을 작성했습니다. 예를 들어서 200 파운드를 계산하기 위해서 첫번째 가장 큰 단위의 코인을 쓸 것인지부터 몇개를 쓸것인지 결정하여서 나머지 돈에 대해서 그 다음 단위의 코인을 이용하여 경우의 수를 따졌습니다. 코인의 금액을 200, 100, 50, 20, 10, 5, 2, 1 을 각각 으로 놓는다면, 경우의 수 를 금액 n에 대하여 i 이상에 대한 코인으로 조합하는 경우의 수라고 한다면, 다음과 같이 재귀적인 표현이 가능합니다. 이 방식을 이용해서 프로그램을 작성하면 다음과 같습니다. 프로그램은 참고용으로만 봐주세요. #include int getcomb(int n, int d); int main() { printf("Ans = %d\n", getcomb(200,..
2015. 3. 30.
프로젝트 오일러 #29 서로 다른 n제곱 개수
이번 문제는 중복을 처리하는 문제이기는 하지만, 숫자의 범위가 큰 까닭에, big integer를 써서 처리를 하든지, 아니면 무언가 다른 방도를 생각해서 해주어야 합니다. 서로 다른 n제곱 갯수를 구하기 위해서는 다음과 같은 생각을 좀 해주어야 합니다. 서로 다른, a, b (b > a) 에 대하여, \(a^m\), \(b^n\)이 갈은 수가 되기 위해서는 반드시, b는 a의 제곱승이어야 합니다. 그렇지 않다면, 같은 숫자가 나올 수가 없습니다. 이것을 토대로 해서 프로그램을 작성해보았습니다. 전반부 프로그램은 제곱수가 아닌 a 에 대하여 \(a^k\)을 모두 체크하고, 그 때의 연산 결과를 1승만 가능한 경우, 2승까지 가능한 경우, 3승까지 가능한 경우 등등으로 나누어서 그 출력값을 미리 v란 배열..
2015. 3. 7.