항상 말썽을 일으키는 청개구리는 밤새 논으로 뛰어 들어 벼를 밟곤 한다.

농부는 아침에 벼가 쓰러진 상태를 보고 밤새 몇 마리의 청개구리가 논을 지나갔는지 알아내려고 한다.

논에는 벼가 일직선으로 심어져 있다. 각각의 벼가 심어진 지점에 남겨진 흔적을 살피면 그 지점을 몇 마리의 청개구리가 밟고 지나갔는지를 알 수 있다.

예를 들어 벼가 심어진 지점과 각 지점을 밟고 지나간 청개구리의 수가 <그림 1>과 같다고 하자.

(원은 벼가 심어진 지점, 원 안의 숫자는 밟고 지나간 청개구리의 수이다.)

모든 청개구리는 논의 왼쪽에서 들어와 일정한 간격으로 뛰어 벼를 밟고 오른쪽으로 나간다.

가장 왼쪽 지점부터 청개구리가 처음 밟는 지점까지의 간격은 청개구리의 뛰는 간격보다 작다.

중간에 방향을 바꾸는 경우는 없으며 벼가 심어진 지점 이외에 다른 지점을 밟는 경우도 없다.

청개구리의 뛰는 간격은 한계가 있어 6이하이고, 또한 논에 들어오면 적어도 두 곳을 밟아야 밖으로 나갈 수 있다.

<그림 1>과 같은 모습은 네 마리의 청개구리가 들어와 <그림 2>와 같이 논을 밟고 나가면 생길 수 있다.

다섯 마리의 청개구리가 들어와 < 그림3> 과 같이 논을 밟고 나가도 <그림 1>과 같은 모습이 가능하다.

벼가 심어진 각 지점마다 지나간 청개구리의 수가 주어질 때,

밤새 지나간 최소 청개구리 수와 이들 각각이 어떻게 지나갔는지 그 경로를 구하여 출력하는 프로그램을 작성 하시오.

청개구리 timer 1s memory 128MB

청개구리 1s 128MB