소는 왜 길을 건너갔을까? 그 이유 중 하나는 그냥 길이 많아서이다.

존의 농장은 N^2개의 작은 정사각형 목초지가 N \times N 격자 정사각형 형태로 이루어져 있다.

기본적으로 소들은 인접한 목초지 사이를 자유롭게 동서남북으로 이동할 수 있고,
농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

소들은 다른 목초지로 이동하는 과정에서 길을 건너야 하는데, 길을 건너는데 T초가 소모되며, 길을 세 번 건널 때마다 풀을 한 번 먹어야 한다.
(이는 출발할 때는 해당되지 않지만, 도착할 때도 해당된다)

또한 목초지마다 풀이 자란 정도가 다를 수 있기에 풀 먹는 시간이 상이할 수 있다. (높이 1의 풀을 먹는데 1초가 걸린다)

소가 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 목초지까지 가는데 걸리는 최소 시간을 알아보자.

소는 왜 길을 건너갔을까? 7 timer 2s memory 512MB

소는 왜 길을 건너갔을까? 7 2s 512MB