어떤 여행가가 일주일동안 호텔에 묵게 되었다.

매일 숙박비로 100달러 호텔측에 지불해야 하는데
일주일 후에야 돈이 생긴다.
그래서 일주일 동안은 하나에 100달러짜리 금링을 호텔에 지불했다가
일주일 후 돈이 생기면 700달러를 내고 금링을 다시 돌려 받기로 했다.

그런데 7개의 금링은 사슬 형태로 이어져 있어서 한개씩 지불하려면
끊어야 한다. 나중에 끊어진 링을 다시 붙이려면 세공비가 필요하므로
여행가는 최소의 링을 자르고 싶다 . 어떤 방법으로 링을 끊어여 최소 세공비만으로
숙박비를 해결할 수 있을까?
( 예를 들자면 마지막링을 제외하고 6개의 링을 자르면 모두 분리 되므로
호텔측에 첫날은 1개 둘째날은 또 하나 더 주어서 두개 , 이런식으로 지불 가능하지만
6개의 링을 끊어서 세공비가 많이든다.)


답은 밑에














































1 2 3 4 567
OOOOOOO

3번 링을 끊으면 1개짜리 링(3번), 2개짜리 링(1,2) , 4개 짜리 링(4567)로 분리 된다.

첫날은 3번 링을 주고 (호텔 3)
둘째날은 12번 링을 주고 3번을 돌려 받고 (호텔 12)
세째날은 다시 3번링을 호텔측에 주고 (호텔 12 3)
네째날은 12번링과 3번링을 돌려받고 4567링을 준다 (호텔 4567)
다섯째날은 3번링을 주고 (호텔 4567 3)
여섯째 날은 12번 링을 주고 3번을 돌려 받는다. (호텔 4567 12)
일곱째날은 3번링를 준다. (호텔 4567 12 3)