jimbo95   2년 전

항상 말썽을 일으키는 청개구리는 밤새 논으로 뛰어 들어 벼를 밟곤 한다.농부는 아침에 벼가 쓰러진 상태를 보고 밤새 몇 마리의 청개구리가 논을 지나갔는지 알아내려고 한다.

논에는 벼가 일직선으로 심어져 있다. 각각의 벼가 심어진 지점에 남겨진 흔적을 살피면 그 지점을 몇 마리의 청개구리가 밟고 지나갔는지를 알 수 있다. 예를 들어 벼가 심어진 지점과 각 지점을 밟고 지나간 청개구리의 수가 <그림 1>과 같다고 하자.(원은 벼가 심어진 지점, 원 안의 숫자는 밟고 지나간 청개구리의 수이다.)

모든 청개구리는 논의 왼쪽에서 들어와 일정한 간격으로 뛰어 벼를 밟고 오른쪽으로 나간다. 가장 왼쪽 지점부터 청개구리가 처음 밟는 지점까지의 간격은 청개구리의 뛰는 간격보다 작다. 중간에 방향을 바꾸는 경우는 없으며 벼가 심어진 지점 이외에 다른 지점을 밟는 경우도 없다. 청개구리의 뛰는 간격은 한계가 있어 6이하이고, 또한 논에 들어오면 적어도 두 곳을 밟아야 밖으로 나갈 수 있다. 

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

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

벼가 심어진 각 지점마다 지나간 청개구리의 수가 주어질 때, 밤새 지나간 최소 청개구리 수와 이들 각각이 어떻게 지나갔는지 그 경로를 구하여 출력하는 프로그램을 작성 하시오.

---------------------------------------------------------------------------------------------------------------------------------------------------

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

그림 3에서 3번 째 줄은 가장 왼쪽 지점부터 처음 밟는 지점까지의 간격이 청개구리의 뛰는 간격이랑 같은거 아닌가요?

저런 경우는 제외하고 푸는거죠?

djm03178   2년 전

가장 왼쪽 지점이라는 게 논을 벗어난 곳이 아니라, 첫 번째 벼가 심어진 지점을 말하는 것으로 해석해야 할 것 같네요. 거기서부터 세면 3칸 움직인 거니까요.

jimbo95   2년 전

답변 감사합니다

댓글을 작성하려면 로그인해야 합니다.