(C++) 백준 13305 주유소

1. 문제

www.acmicpc.net/problem/13305

13305번: 주유소

 

2. 풀이

왼쪽에서 오른쪽으로만 갈 수 있으므로 

눈앞에 닥친것부터 해결해야하는 전형적인 그리디 알고리즘 문제이다.

 

따라서 나는 temp에 첫번째 원소를 두고 만약 temp보다 새로나온 원소가 작다면 temp를 업그레이드 시킨 후

temp에 거리를 계속 곱했다.

 

예를들어

거리                  5         3           1

기름값       3          5         2           2

 

일때,

1.

temp = 3으로 둔 뒤

ans += temp * 5

2.

temp < 5 // temp는 여전히 3

ans += temp * 3

3.

temp > 2 

temp = 2 업그레이드

ans += temp * 1

4. 

temp == 2

ans += temp *0

 

이런 방식으로 해결했다!!

 

그런데 문제가 있었으니..... 

바로 자료형이었다! 

자료 형을 모두 longlong으로 바꾸니 해결되었다!^^7

 

3. 코드

github.com/gimkuku/Algorithm/blob/master/Greedy/13305.cpp

gimkuku/Algorithm

 

4.

이걸로 그리디 백준이 끝났다! 

낼부턴 동적계획법을 풀어볼 예정~.~

 

안풀린다면 댓글 달아주시면 코드 봐드릴게용:D