[백준] 단계별로 풀어보기(단계:16,그리디 알고리즘,JAVA)13305번, 주유소

문제 링크

13305번: 주유소

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그리드 알고리즘(탐욕 알고리즘)이란 여러 경우를 선택해야할 때 그 상황에 최적의 경우으로 생각하는 것을 반복하여 최종적인 답을 가져오는 방법입니다.

 

이 문제에서 최소의 기름가격을 얻으려면 현재 기름가격보다 작은 가격을 가진 위치를 파악하고 그 위치까지만 갈 수 있는 기름만 구매하여 이동한 뒤 작은 가격에 위치에서 다시 위에 내용을 반복하여 목적지까지 도달하면 됩니다.

 

예제 입력1을 보면 

첫 시작 위치의 기름값 = 5이어서 현재 위치의 기름값은 5가 됩니다.

 

이후 경유지에 현재 기름값보다 작은 기름값을 가진 곳까지 이동합니다.

 

현재보다 작은 기름값을 가진 경유지는 다음 경유지입니다.

 

그래서 다음 경유지까지 이동할 수 있는 거리에 기름만 넣기 때문에 5 × 2 = 10이 첫 시작위치에서 지불하였으며

 

다음 경유지에 기름값을 현재 기름값으로 변경하여 그 이후 방금 전에 했던 방법을 반복하여 도착지까지 가는 것입니다.

 

과정 : 

 

현재 기름값 : 5 ->현재 기름값보다 작은 기름값을 가진 경유지 발견 -> 경유지까지 이동할 수 있는 기름 구매 및 이동(5×2=10) 

 

현재 기름값 : 2 -> 도착지점까지 경유할때 작은 기름값 없으므로 도착지까지 이동(2 × 4 = 8) -> 목적지 도착

 

최종 지불한 금액 : 10 + 8 = 18으로 최소값은 18이 됩니다.

• 거리값과 기름값을 저장하는 배열 distance,oilPrice를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기 기준으로 나누어 배열에 저장하였습니다.
• 목적지까지 최소로 사용하는 기름값을 구하는 함수 minOilPirce를 만들었습니다.
• 함수 결과를 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 결과를 출력하였습니다.

• for문을 통해서 위에서 설명했던 알고리즘을 반복하여 최소값을 구하였습니다.
• return을 사용하여 최소값을 반환하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int index;
	static int[] distance;	//거리 저장 배열
	static int[] oilPrice;	//기름 가격 저장 배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //---------입력값 저장 및 배열 초기화-----------
    	index = Integer.parseInt(br.readLine());
    	distance = new int[index-1];
    	oilPrice = new int[index];
    	
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<index-1;i++)
    		distance[i] = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<index;i++)
    		oilPrice[i] = Integer.parseInt(st.nextToken());
    	
    	bw.write(minOilPrice() + "\n");	//함수 호출 및 결과 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
    //----------최소 기름값 구하는 함수---------------
	public static long minOilPrice() {
		long currentPrice=oilPrice[0];
		long result=distance[0]*currentPrice;
		for(int j=1;j<index-1;j++) {
			if(currentPrice>oilPrice[j]) {
				currentPrice=oilPrice[j];
			}
			result += distance[j]*currentPrice;
		}
		return result;
	}
}