[백준/c++] 13305번: 주유소

 

 

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

도시 N개, 제일 왼쪽에서 오른쪽으로 이동

이동 1km마다 1리터 기름 사용

최소 비용 구하기

 

그리디 알고리즘으로 해보자. 그리디 알고리즘은 현재 상황에서 최적의 해를 선택하면 되는데

그리디 문제를 좀 풀어보니까 규칙을 찾아야 문제를 풀기 쉬워진다. (당연한 소릴...)

예제가 많이 있으면 좋은데,, 문제에서 보여주는 예제는 2개 뿐이다.. 

일단 1번째 예제를 보면서 어떤 규칙이 있을까 찾아봤다.

 

         2             3              1 

(5) ----- (2) ----- (4) ----- (1)

 

 

IF 현재 내가 있는 주유소의 기름 값이 다음 주유소보다 비싸면, 여기선 최소 기름을 넣어야 한다.

    그러므로 다음 주유소까지 갈 수 있는 기름만 넣어주면 된다.

 

ELSE 현재 내가 있는 주유소의 기름 값이 다음 주유소보다 싸면 여기서 기름을 더 넣어줘야 하는데,

          얼마만큼의 거리의 기름을 이 주유소에서 넣어줘야 할지 계산해야 한다. 이를 위해 for문을 넣어준다.

          for(int j = 현재 위치 다음(i+1); j<n; j++) //끝까지 이 주유소보다 비쌀 수 있기 때문에 j<n

              sum 거리 합계

              만약 이 주유소보다 싸다면 나오기 - 현재 주유소 기름 값 * 거리 합계를 총 비용에 더해준다.

 

뭐 이런식으로 정리해준다.

 

이 문제는 서브테스크가 있는데, 예제 2를 봐도 된다.

모든 주유소의 기름 값이 1로 동일한 경우를 보여주는데 이 경우 IF 조건에는 들어가지 않는다. ELSE로 들어가서 j이 n-1가 될때까지 돌며 거리 합계(sum)을 구하고 j == n이 되면서 for문을 종료하며 나온다. 이러면 i가 시작점에 계속 있으므로 if문을 통해 "끝"이 났으므로 ans 값을 갱신해주며 더 진행하지 않고 전체 for문을 종료하도록 해준다. 

 

그리고, 한가지 반례가 있는데

ex1)

4

2 3 1

5 2 4 1

> 18

 

ex2)

7

3 4 2 2 4 5

8 9 5 4 2 7 1

>92

 

이 두가지 예제는 다른 형태를 띈다. ex1의 경우 ELSE문을 통해 1번 주유소(2)에서 n-1번까지 기름을 모두 구매하지만 ex2의 경우 0번 주유소(8)에서 ELSE로 들어가서 진행하고 뒤에 다른 주유소가 더 남아있다. 이렇게 되면 i를 갱신해주는 작업을 다르게 해줘야 한다.

ex1의 경우, j가 n-1가 되어 제일 오른쪽 도시에 도착하게 되는 경우이므로 i = j

ex2의 경우, 다음 주유소가 남은 경우이므로 i = j-1로 갱신해줘야 한다. 왜냐면.. break를 통해 나오고 계속 for문이 돌아가서 i++ 되기 때문..! 

 

후.. 이것 때문에 머리를 좀 굴렸다..

 

역시 이런 문제는 반례를 생각해보고 여러 예제를 직접 만들어보면서 풀어줘야겠다.

연습 문제니까 질문 게시판에 올라오는 사람들의 반례를 볼 수 있지만, 코테를 진행하면 그런 반례는 내가 찾아내야 하니까 스스로 할 수 있는 능력을 길러야겠다..!!

화이팅이여~~~

 

쩝..^^ 첫번째 제출 땐 1번 테스트만 통과했다는...🤷‍♀️