최단시간 구하는 문제입니다. 한번 풀어보세요^^

athxue의 이미지

네이버 돌아댕기다가 발견한 문제인제 재밌네요. 혹시 모르시는 분들은 답을 검색하기 전에 풀어보세요.

갑, 을, 병, 정 네 사람이 강을 건너려고 한다. 그런데 강에는 배가 한 척밖에 없고, 그 배에는 최대 두 사람이 탈 수 있다. 혼자서 배를 타고 노를 저어 강을 건널 경우 갑은 1분, 을은 2분, 병은 5분, 정은 10분의 시간이 걸린다. 둘이서 함께 배를 탈 경우, 안전을 위해 더 천천히 노를 젖는 사람이 노를 잡는다. (예를 들어 을과 병이 함께 배를 탈 경우, 병이 노를 잡게 되고, 따라서 강을 건너는데 5분이 걸린다.) 네 사람이 무사히 강을 건너려면 최소 몇 분이 걸릴까?

Stand Alone Complex의 이미지

윽 실수! 다시 생각해봐야겠습니다!

RET ;My life :P

익명사용자의 이미지

갑을 2분

돌아올때 갑 1분

갑병 5분

또 갑 1분

갑정 10분

해서 합이 19분

hogi2271의 이미지

갑을 갑병 갑정

^^/

JuEUS-U의 이미지

갑을 갑병 갑정은 너무 식상해서 -ㅅ- 대충 이리저리 바꿔보니 17분 뜨네요...

[섬1] (배) [섬2] 입니다 =ㅅ=

[갑을병정] _()_ [] !!!

[병정] (갑을)→ [] 2분
[병정] ←(을) [갑] 2분
[을] (병정)→ [갑] 10분
[을] ←(갑) [병정] 1분
[] (갑을)→ [병정] 2분

[] _()_ [갑을병정] !!! 합계 : 17분

헉헉헉....

achiven의 이미지

이 문제 유명하죠..ㅎㅎㅎ

superwtk의 이미지

수영해서 건너면 안되나요

--------------------------------------------------------------------------------
http://blog.superwtk.com

esrevinu의 이미지

19분으로 생각하고 있다가 다시 들어와 보니 17분도 되네요.
이런 문제를 해결하는 수학은 무엇일까요?

이걸 증명이라고 할 수 있을지는 모르겠지만...

갑,을,병, 정이 노를 저으며 건너편으로 가는 횟수를 각각 A, B, C, D라 하고,
돌아오는 횟수를 각각 a, b, c, d라고 하자.
 
걸린 시간은 x = (A+a) + 2(B+b) + 5(C+c) + 10(D+d) 이다.
생각할 수 있는 조건은 
A+B+C+D = 3, a+b+c+d = 2. (물론 더 많을 수 있지만 그건 고려치 않음. 즉 여기서는 건너편으로 갈 때는 두명, 돌아올 때는 한명만 오는 것만 고려함.)
A = 0, D >= 1, d < D.
따라서
x = 8 + 3C + 8D + b + 4c + 9d.
  >= 16 + 3C + b + 4c + 9d  (D >= 1 이므로)
  = 16 + 3C + b + 4c (위 값은 D = 1일 때의 값이므로 d < D 조건에 의해 d = 0)
 
여기서 가능한 가장 작은 값은 C = 0, b = 0, c = 0일 때 16이다.
그러면 A = 0, B = 2, C = 0, D = 1, a = 2, b = 0, c = 0, d = 0.
하지만 B = 2 이기 위해서는 b >= 1이어야 한다. 왜냐하면 돌아올때는 한 명만 돌아오고, 또 돌아와야만 건너갈 수 있기 때문이다. 따라서 이 답은 허용되지 않는다.
따라서 그 다음으로 가능한 경우는 A = 0, B = 2, C = 0, D = 1, a = 1, b = 1, c = 0, d = 0 이고 시간은 17이다. 이 경우는 JuEUS-U가 예를 들어 보였으므로 최소 시간은 17이다. Q.E.D
cppig1995의 이미지

임백준님께서 쓰신 책에 17분이라고 나왔다.
Q.E.D (Quod Erat Demonstrandum)
죄송합니다.
------------------------------------------------------
In simplexitate est opportunitas. --cppig1995
"x86-64 운영체제를 만들자" 강좌: http://kldp.org/taxonomy/term/3663
2007학년도 대전월평중학교 1학년 3반 학급카페: http://103.wo.tc

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

ratsbomb의 이미지

만약, 문제 밑에 첨부로,
"단, 한 번 건너간 사람은 다시 건너올 수도 있다"
라고 적어둔다면, 다들 쉽게 풀지 않을까요?

정답을 알고 난 뒤 들었던 생각입니다.

/**
* We need Divide and Conquer 美德
* @return Nothing
*/

白頭山石磨刀盡,豆滿江水飮馬無,男兒二十未平國,後世誰稱大丈夫

ydhoney의 이미지

3초? 
 
====================여기부터 식은어치====================
안녕하세요. 저는 야동 초등학교 2학년 6반 11번입니다!! 제 컴퓨터에 리눅스를 깔아보고 싶습니다. 리눅스라는건 어제 처음 들어 보았습니다.
리눅스에서도 카트라이더는 되겠지요? 설마 안되나요? 안되면 왜 쓰나요? =3=33 리눅스에서는 카트라이더 캐릭터 머리가 너무 커서 못받아들이나요?