leehosu01   1년 전

 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러번 이용할 수도 있다.

첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고,오민식이 무한대의 돈을 벌 수 있을 때는 “Gee"를 출력한다.



어떻게 주어진 방향으로만 가면서 헤밀턴을 만들죠????


최대 경로는 길이가 |E|에 불과한데 무한번 돈다는게 불가능할텐데 


문제맞추신분들 존경 합니다  어떻게 푸신건지

jh05013   1년 전

"오민식이 돈을 버는 돈보다 쓰는 돈이 많다면, 도착 도시에 도착할 때 가지고 있는 돈의 액수가 음수가 될 수도 있다. 또, 같은 도시를 여러 번 방문할 수 있으며, 그 도시를 방문할 때마다 돈을 벌게 된다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러번 이용할 수도 있다."

leehosu01   1년 전

먼저 입력된 교통수단을 이후에 사용할수없지요?

그러니까 i번 간선을 e(i)로 하면

e(i) -> e(i+1) 가능 

e(i) -> e(i-1) 불가능 

e(i-1) -> e(i+1) 불가능 인데 

이상황에서 

 이동 경로1) e(0) -> e(1) -> e(2) -> e(5) 

 이동 경로2) e(0) -> e(1) -> e(2) -> e(6) 

꼴로 갈때 e(i) -> e(i+t)  (단,t>=0 이유:: 동일 간선 사용가능)

꼴로만 이용 가능 하고, t>0인 경우 발생시 더 사용 가능한 간선수 감소 & t==0 인 채로 있으려면 (시작)==(끝)  이 성립해야 하는데 



.

.

..? 


혹시  (시작)==(끝)  이것 때문인가요?



jh05013   1년 전

"입력으로 주어진 방향으로만 이용"이란 말을 오해하신 것 같습니다. 저건 a->b로 가는 도로가 주어졌을 때 그 도로를 b->a 방향으로 쓸 수 없다는 뜻입니다.

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