[Java] 다리 bridge - Uva 10037 문제

[Java] 다리 bridge - Uva 10037 문제

문제설명

 

내 코드

 

 

👑 Key Point

len<=2이면 손수 계산 해도 되지만,

 

len>2라면 이 때부터 최소가 되는 거리는 두가지 Case로 나뉜다. 최소가 되는 것은 이 두가지 중 하나 밖에 없음 

 

 

Case 1 : dis[1]*2+ dis[0]+dis[j]  : 처음 최소거리 2개(dis[0], dis[1]) 를 먼저 옮긴뒤 첫번째(dis[0])가 플래쉬를 가지고 되돌아 오고 ,맨 끝에 있는 최대의 거리 두가지(dis[j-1]+dis[j]) 를 같이 옮긴뒤 최소에서 두번째 dis[1]가 플래쉬를 가지고 되돌아오는 경우에 걸리는 거리
Case 2 : 2*dis[0]+dis[j]+dis[j-1]  : 처음 최소거리랑 최대거리 (dis[0], dis[j]) 를 먼저 옮긴뒤 첫번째(dis[0])가 플래쉬를 가지고 되돌아 오고 ,처음 최소거리랑 그다음 최대거리 (dis[0]+dis[j-1]) 를 같이 옮긴뒤 최소거리 dis[0]가 플래쉬를 가지고 되돌아오는 경우에 걸리는 거리

if(dis[1]*2+ dis[0]+dis[j]<2*dis[0]+dis[j]+dis[j-1])

두가지를 for문에 넣고 비교한뒤 더 적게 걸리는 거리를 실행하고 j는 -2 시킨다.

 

여기까지가 최대거리 dis[j-1], dis[j] 두 개를 최소의 거리로 다리를 건너게 하고 플래쉬는 다시 처음에 있게 하는 방법이였음.

 

이것을 j가 2이하가 될때까지 반복.

 

응용된 Greedy 문제인데 알고보면 재밌는 문제!