영국 동전을 이용해서 푸는 문제라고? 여행을 즐기는 나에게 딱 맞는 문제가 나왔군. 좋아, 집에 모아 둔 영국 동전들을 꺼내서 한번 풀어 볼까?
이번 문제는 영국 동전을 가지고 풀어야 한다. 바로 영국에서 사용하는 파운드(£)와 펜스(p)다. 문제에 사용할 동전의 종류는 아래와 같다.
이 동전들을 가지고 2파운드를 만드는 방법은 다양하다. 가장 쉬운 건 2파운드 동전 그 자체다. 조금 복잡한 예를 하나 들면 다음과 같다.
오일러 프로젝트 31번 문제는 영국 동전 8가지 종류를 가지고 2파운드를 만드는 서로 다른 방법은 모두 몇 가지인지 찾는 것이다.
12진법, 20진법 사용한 영국 화폐 체계
영국 화폐의 역사는 8세기까지 거슬러 올라간다. 오파 왕(재위 757~796년)이 은으로 만든 ‘페니’라는 동전을 도입한 뒤부터 화폐 체계가 발전했다. 무게 단위인 파운드가 통화 단위로도 쓰이게 된 이유는 금화 하나를 1파운드 무게의 은과 교환할 수 있었기 때문이다.
흥미로운 점은 화폐 체계가 정립되는 과정에서 현재 사용되는 10진법이 아닌 12진법과 20진법이 쓰였다는 사실이다. 페니의 복수형이 ‘펜스’이고, 페니와 파운드 사이에 ‘실링’이라는 화폐 단위가 하나 더 있었다. 1실링은 12펜스였고, 1파운드는 20실링으로, 바로 이 실링과 페니, 실링과 파운드 사이에 12진법과 20진법 체계를 적용했던 것이다. 즉 1파운드(100펜스)는 지금과 달리 240펜스였다.
실링 외에도 영국에서는 5실링의 가치를 가진 ‘크라운’과 21실링에 해당하는 ‘기니’ 등 복잡한 화폐 체계를 사용했다. 하지만 현재는 페니(펜스)와 파운드로 통일하고 나머지는 사용하지 않는다. 1971년 화폐 개혁을 하면서 1파운드를 240펜스가 아닌 100펜스로 바꾼 결과다. 영국에서는 화폐에 10진법 체계를 도입한 1971년 2월 15일을 ‘10진법의 날’로 부른다.
이후 1실링의 가치는 5펜스로 바뀌었고, 자연스럽게 이전부터 사용되던 5펜스와 10펜스 동전이 1, 2실링을 대체하게 됐다. 화폐 개혁 후에도 과거에 발행된 실링은 시중에서 쓸 수 있었지만 1, 2, 5, 10, 20, 50펜스와 1, 2파운드 동전이 자리를 잡으면서 점차 사라지게 됐다. 하지만 과거 영국의 영향을 받았던 나라 중 이집트 같은 나라에서는 지금도 기니와 같은 단위가 통용된다.
이처럼 복잡한 화폐 단위 때문에 제2차 세계대전 당시 영국에서는 간첩을 잡을 때 물건을 사고 계산하는 모습을 유심히 살폈다고 한다. 10진법에 익숙한 간첩들이 상점에서 물건을 사고 잔돈을 계산할 때 자연스럽지 못하고 혼란스러워하는 모습을 보였기 때문이다.
특이하게도 영국에서는 한 번에 지불할 수 있는 동전의 액수를 ‘주화법(Coinage Act)’으로 정해두고 있다. 예를 들어 1페니와 2펜스는 20펜스를 초과해서 지불할 수 없고, 5펜스와 10펜스는 5파운드를 초과할 수 없다. 또 20펜스와 50펜스는 10파운드를 초과해서 지불할 수 없다. 다만 1파운드 이상의 동전은 제한 없이 낼 수 있다.
아이작 뉴턴과 영국 여왕
화폐에서 빼놓을 수 없는 게 위인의 얼굴이다. 1978년~1988년 사이에 발행한 영국 1파운드 지폐에는 수학자이자 과학자였던 아이작 뉴턴의 얼굴이 들어가 있다. 주기적으로 화폐에 그려 넣는 주인공을 바꾸고 있지만 여왕의 얼굴만큼은 빼놓지 않고 들어간다. 흥미로운 점은 화폐가 발행되는 시점의 여왕의 모습을 그린다는 점이다. 따라서 자세히 살펴보면 같은 지폐라도 과거에 발행한 지폐와 최근 발행한 지폐에 그려진 엘리자베스 2세의 얼굴이 다르다는 것을 알 수 있다. 자, 이제 다양한 영국 동전을 써서 2파운드를 만드는 경우의 수를 찾아보자!
오일러 프로젝트 31번 문제를 해결하려면?
이번 문제는 컴퓨터과학 분야에서 많이 알려진 유형으로, 흔히 ‘동전교환문제(Coin Change Problem)’라고 불러요. 이 문제는 여러 가지 방법으로 풀 수 있어요. 반복문을 써서 경우의 수를 일일이 구할 수도 있고, 함수가 자기 자신을 다시 호출하는 ‘재귀(recursion)’ 기법을 쓰면 몇 줄 짜리 코드로도 풀 수 있답니다. 어떤 방법이든 좋으니 일단 나름대로 해결을 한 다음에, 다른 사람들의 풀이를 살펴보면 더 흥미로울 거예요.
이제 1p(페니) 동전의 개수부터 2p 동전의 개수, 200p 동전의 개수까지 각각을 a, b, c, d, e, f, g, h라고 해 볼게요. 그러면 이 문제는 다음 식을 만족하는 a, b, c, d, e, f, g, h의 조합이 몇 가지인지를 묻는 셈이 되죠.
가장 단순하게 풀려면, 동전별로 개수를 일일이 0개, 1개, 2개, 3개 등으로 바꿔가면서 그 때의 동전 조합이 2파운드를 만드는지 검사하는 방법이 있겠죠. 그러면 동전 종류별로 반복문이 하나씩 나오는 형태가 될 거예요. 코딩하는 방법에 따라서는 큰 수에서 작은 수로 줄어들면서 거꾸로 반복할 수도 있고, 1보다 큰 간격으로 증가 혹은 감소시킬 수도 있겠네요. 여러분이 사용하는 프로그래밍 언어에서 반복문을 어떻게 쓰는지 먼저 잘 알아 두세요.
재귀 기법을 이용하려면 먼저 한 종류의 동전을 택하세요. 그러면 두 가지 선택을 할 수 있어요. 2파운드를 만드는 데 그 동전을 쓰거나, 안 쓰거나죠. 쓰지 않는다면 나머지 동전 종류로 똑같은 금액을 만드는 가짓수가 있을 거예요. 쓴다면 나머지 동전 종류로 해당 동전의 액수만큼을 뺀 금액을 만드는 가짓수도 있고요. 답은 두 경우의 가짓수를 더한 것이 돼요. 재귀는 이런식으로 만들 금액이 0이 되거나 더 이상 제외할 동전 종류가 없을 때까지 계속 구하는 방식이에요. 프로그래밍에 익숙하지 않은 사람에게는 이 방식이 좀 어렵기 때문에, 관련된 공부를 먼저 하고 도전하는 것을 권합니다!
