[백준 Java] 13305 주유소

문제 링크

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

접근 방법

음~
잘못 생각한 방법

• 거리 중 가장 싼 도시를 고름
• 그 도시에서 남은 거리 모두 충전
• 다른 거리는 다음 도시로 가기 위해 필요한 거리 만큼만 저장

➡️ 이랬더니 17점 나옴

 

올바른 풀이

• 순서대로 탐색하면서 이전보다 싸면 최소값으로 갱신
• 해당 도시의 거리만큼 가장 싼 곳에서 충전

처음에 첫번째 도시를 최소값으로 설정하고, 두번째 도시로 가기 위한 비용을 설정해준다.

for문은 2번째 도시부터 N만큼 탐색한다.

탐색하면서 현재 주유비용이 이전보다 싸다면 최소값을 갱신해준다.

다음 도시로 가기 위해 해당 거리는 꼭 충전을 해줘야 하기 때문에 현재 최소값으로 주유한다.

 

input 반복문을 두번 돌리고 마지막에 다시 반복문을 돌면서 탐색을 했는데, 도시 주유 비용 입력 받으면서 한번에 처리 해도 돼서 코드를 수정했다.

시간은 O(N)이 됨.

 

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        //도시 사이 거리
        long[] dist = new long[N - 1];
        for (int i = 0; i < N - 1; i++) {
            dist[i] = Integer.parseInt(tokens.nextToken());
        }

        tokens = new StringTokenizer(br.readLine());
        int cost = Integer.parseInt(tokens.nextToken()); //가장 처음 값

        //초기값 설정. 처음 도시는 다음 거리만큼 충전해야 함
        long min = cost;
        long result = min * dist[0];

        //두번째 도시부터 설정
        for (int i = 1; i < N-1; i++) {
            cost = Integer.parseInt(tokens.nextToken());
            min = cost < min ? cost : min; //이전 값이랑 비교해서 싼 값 저장
            result += (min * dist[i]);
        }// end input

        System.out.println(result);

    }
}