[BaekJoon] 백준 13305번 _ 주유소 for JAVA _ 그리디 알고리

 

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

13305번: 주유소

 

 

 

 

 

문제

 

 

 

---

 

 

내가 푼 방법은 

 

 

 

 

기름값이 싸면 만땅 충전해서 가는게 좋음

 

그래서 이전 기름값과 비교해서 작은곳에서 다음다음 갈 것 까지 만땅 충전해서 가는것이다...

 

 

그러니까 기름값 싼 곳을 찜해놓고 다음 기름값, 다다음 기름값, 다다다음 ... 이렇게 비교해서 작은곳에서 만땅 넣는다.

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek13305 {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int city = Integer.parseInt(br.readLine());
		StringTokenizer st;
		long count = 0;
		
		
		long[] liter = new long[city];
		long[] need = new long[city - 1];
		
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i =  0; i < city-1; i++) {
			
			need[i] = Long.parseLong(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i =  0; i < city; i++) {
			
			liter[i] = Long.parseLong(st.nextToken());
		}
		
		long min = liter[0]; // 첫번째 마을의 리터당 가격을 min으로 설정
		for(int i = 0; i < city - 1; i++) {
			if(min > liter[i]) min = liter[i];
			
			count += (min * need[i]);
		}
		
		System.out.println(count);
		
	}
}

 

 

 

그렇다....

 

처음에 처음 가격을 min으로 안하고 그냥 뭐랄까... 하나하나 기름값을 앞뒤로 비교했더니 17점 나왔다. (서브태스크)

 

 

암튼 그래서 다른 블로그를 좀 참고했고.. (https://st-lab.tistory.com/192)

 

 

음~ 그리고 중요한거

 

 

리터당 가격은 1 이상 1,000,000,000 이하의 자연수 이므로 int가 아닌 long 타입을 사용해야 오류가 없다.

 

 

이거때매 58점 두번나옴ㅠㅠ

 

 

 

 

성능