donghy9508   6년 전

먼저 설 연휴 좋은 시간 질문을 봐주셔서 감사드립니다.


아래 코드는 그리디 전략으로 연료채우기를 푼 코드입니다.

최소로 가기 위해 가장 멀리갈수 있는 주유소(가장 많은 연료량을 얻을 수 있는) 부터 먼저 방문해야 한다고 생각했습니다. 

그러기 위해 힙(최대) 자료구조(삽입 삭제가 모두 logn)를 이용해서 어떤 주유소를 방문할 수 있을때 가장 많은 연료를 얻을 

수 있는 주유소를 방문하고 그때 연료를 갱신해주는 방법으로 문제를 해결했습니다. 그러나 이해가 되지 않는 부분이 

있습니다. 아래 첨부한 소스코드는 틀린 코드입니다.


주석처리한 for 루프문이 맞는 코드입니다.



1)갈 수 있는 주유소에서 가장 많은 기름을 주는 주유소의 기름을 현재 기름에 더하는 것과(주석처리한 for문)

2)갈수있는 주유소가 주는 기름+현재기름 중 최대로 현재 기름을 갱신하는 것은 아무리 생각해도 차이가 없어 보이는데


2)의 방법은 자꾸 틀렸다고 합니다. 반례 테스트 케이스가 존재하지 않는다고 생각되는데 

2)의 방법이 왜 틀렸는지 알고 싶습니다.  부탁드립니다.


marco2520332   6년 전

4

4 1

5 1

11 3

15 10

25 10


이 예제를 제대로 풀게 되면

10 -> 1,1
11 -> 3,1
14 -> 1
15 -> 10
25

>> 답 4 출력

이어야 하는데,

주석처리 되지 않은 반복문 같은 경우에는

10 -> 11,11
11 -> 14,11
14 -> 11
11 (false)

라고 답을 출력합니다.


donghy9508   6년 전

감사합니다. 미처 생각지 못한 부분을 깨달았습니다. 즐거운 설 연휴 되세요!

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