책 이야기

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.

n개의 동전을 서로 다른 방법으로 묶는 방법을 p(n)이라 하자. 예를 들어, 5개의 동전은 일곱 가지 다른 방법으로 묶을 수 있다. 따라서 p(5)=7이다.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

p(n)이 1백만인 n의 최소값을 찾으시오.

--------------------------------------------------------------------------

동전으로 변형되어 있지만 문제 자체는 76번 문제과 동일한 알고리즘으로 해결 가능하다. 즉, 오일러의 오각수 정리 공식을 적용하면 된다. 76번과 차이점은, 76번은 2개 이상의 조합을 요구했기 때문에 전체 숫자에 해당하는 1을 빼야하지만(위 예시에서 동전 5개 묶음을 제외하므로 76번에서 p(5)=6), 이번 문제에서는 그 과정이 필요없다는 것이다.

한가지 고려할 사항은 동전 숫자에 상한선이 없으므로 76번 문제에서 적용했던 방법을 조금 변형시킬 필요가 있었다. 처음에는 상한선을 1만으로 했는데 답이 나오지 않아, 10만으로 바꾸고 나서 답을 구할 수 있었다.

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

영국의 화폐에는 파운드(£)와 펜스(p)가 있다. 통용되는 동전에는 다름 8가지가 있다:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

2파운드는 다음 방법으로 만들 수 있다.

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

동전을 이용하여 2파운드를 만드는 방법에는 몇가지가 있는가?

--------------------------------------------------------------------------

재귀함수 형태도 가능할 것 같았는데, 큰 화폐부터 시작해서 8번 중첩되는 반복문(for loop)을 구성해서 값이 200이 되면 카운트를 증가시키고 다음 단계로 넘어가는 형태로 해결했다.

좀 더 빨리 실행시키기 위해서는 반복되는 계산을 줄이기 위해 이전 반복을 기억하게 하는 메모이제이션, 접근을 다르게 해서 해결하는 동적 프로그래밍 방법이 있다고 하는데 이해하기에는 좀 어려웠다.