영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까?
brute-force로 풀었는데 시간이 상당히 걸린다.
문제 풀이 후 좀 더 찾아보니 전형적인 Dynamic Programming 알고리즘의 문제라고 한다.
아래의 내 코드가 약 1분 정도가 소요되는데
DP 방식으로 구현된 이 코드
http://blog.dreamshire.com/2009/03/31/project-euler-problem-31-solution/
는... 20초안에 결과가 나온다. 코드를 봐도 어떻게 저렇게 풀리는지 이해가 잘 되지 않는다..흠.. 일단 점화식(?)을 찾는 것이 관건인 것 같은데... 그게 잘 안나오네..
> 위 주석부분은 가장 간단한 DP코드인데.. 저건 이해가 되더만...그래도..
Ruby
Perl 알고리즘의 힘을 느낀 문제..