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이 되면 카운트를 증가시키고 다음 단계로 넘어가는 형태로 해결했다.
좀 더 빨리 실행시키기 위해서는 반복되는 계산을 줄이기 위해 이전 반복을 기억하게 하는 메모이제이션, 접근을 다르게 해서 해결하는 동적 프로그래밍 방법이 있다고 하는데 이해하기에는 좀 어려웠다.