[7월의 퍼즐] 쿠키 몬스터

미국의 전설적인 아동용 방송 세서미 스트리트^{Sesame Street}는 다양한 등장인물과 재미있는 내용으로 많은 인기를 끌었다. 세서미 스트리트의 유명 등장인물 가운데 하나로 쿠키 몬스터가 있다. 쿠키 몬스터는 뭐든 닥치는 대로 먹어 치우지만 특히 이름처럼 쿠키를 좋아해서, 쿠키 몬스터가 등장하는 에피소드는 마지막에 쿠키를 마구 먹어 치우면서 끝나곤 했다.

쿠키가 들어 있는 단지 일곱 개가 있다. 쿠키의 개수는 각각 1, 2, 4, 7, 13, 24, 44개이다. 쿠키 몬스터는 이 가운데 몇 개의 단지를 골라 정확히 똑같은 개수만큼 쿠키를 꺼내 먹는다. 이렇게 몇 개의 단지를 골라 쿠키를 꺼내 먹는 것을 한 번으로 칠 때, 최소 몇 번 만에 모든 쿠키를 먹어 치울 수 있을까?

예를 들어, 세 개의 단지에 1, 2, 4개의 쿠키가 있었다면, 두 번째와 세 번째 단지에서 2개씩 꺼내 먹어서 1, 0, 2개를 만들고, 첫 번째와 세 번째 단지에서 1개씩 꺼내 먹어서 0, 0, 1개를 만든 다음, 마지막 쿠키를 먹는 것으로 세 번 만에 모든 쿠키를 먹을 수 있고 이것이 최소 횟수이다.