Today Sulim Learned

silver 4. 주유소 (13305)

06 Feb 2022 | 알고리즘 프로그래밍 자바

silver 4. 주유소 (13305)

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

문제

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성

입력: 첫 줄에는 도시의 개수를 나타내는 정수 N이 주어짐. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이기 제일 왼쪽 도로부터 N-1개의 자연수로 주어짐. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어짐

출력: 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력

풀이

  • 아이디어: 이전 도시의 기름값과 비교했을 때, 현재 도시의 기름값이 더 싸면 현재 도시의 기름값과 다음 도시와의 거리를 곱해 결과값에 더해주고, 이전 도시의 기름값이 더 싸면 이전 도시의 기름값과 다음 도시와의 거리를 곱해 결과값에 더해줌
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    // 필요한 변수 선언
    int N = Integer.parseInt(br.readLine());
    long[] lengths = new long[N-1];	// 도시를 연결하는 도로의 길이
    long[] wons = new long[N];	// 주유소의 리터당 가격
    long result = 0;
    
    // 도로의 길이를 입력받아와 변수에 저장
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i=0; i < N-1; i++){
      lengths[i] = Long.parseLong(st.nextToken());
    }
	
    // 리터당 가격을 입력받아와 변수에 저장
    st = new StringTokenizer(br.readLine());
    for (int i=0; i < N; i++){
      wons[i] = Long.parseLong(st.nextToken());
    }

    long minCost = wons[0];	// 리터당 가격의 최솟값 저장. 처음 리터당 가격을 첫번째 도시의 리터당 가격으로 저장 

    for(int i = 0; i < N-1; i++){
      if (minCost > wons[i]){	// 이전 도시와 리터당 가격을 비교했을 때, 현재 도시의 가격이 더 싼 경우
        minCost = wons[i];	// 리터당 가격의 최솟값을 현재 도시의 가격으로 변경
      }
      result += minCost * lengths[i];	// 리터당 가격의 최솟값과 다음 도시로의 도로 길이를 곱한 후 결과값에 더해줌
    }

    System.out.println(result);
  }
}

Related Posts