백준 13305 자바 및 C++

풀기 전:

이 문제를 푸는 알고리즘은 1)마지막 주유소를 제외한 나머지 주유소에서 가장 싼 주유소에서 나머지 남은 거리를 모두 넣어 버리고 2) 그 주유소 전에 있는 주유소 중 가장 싼 주유소를 찾아서 첫 번쨰 찾은 주유소 까지 거리를 계산해주고...

결국 index값이 0일 때까지 반복해주면 된다!

자바(JAVA):100점

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Collections;
public class Main{
    public static void main(String[] args) throws IOException {
      Scanner scanner=new Scanner(System.in);
      int n=scanner.nextInt();
      int dist[]=new int[n];
      for(int i=0;i<n-1;i++){
          dist[i]= scanner.nextInt();
      }
      int price[]=new int[n];
      for(int i=0;i<n;i++){
          price[i]= scanner.nextInt();
      }
      long total=0;
      int lastIndex=n-1;
      while(true){
          int min=1000000001;
          int minIndex=-1;
          for(int i=0;i<lastIndex;i++){
               if(min>price[i]){
                   min=price[i];
                   minIndex=i;
               }
          }
          long sumDistance=0;
          for(int i=minIndex;i<lastIndex;i++){
              sumDistance+=dist[i];
          }
          total+=sumDistance*min;
          lastIndex=minIndex;
          if(lastIndex==0){
              break;
          }
      }
      System.out.println(total);

    }
}

C++:58점? 자바랑 코드는 같으나 뭐가 문제인지 모르겠다 ㅠㅠ

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	int* dist = new int[n];
	for (int i = 0; i < n - 1; i++) {
		cin >> dist[i];
	}
	int* price = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> price[i];
	}
	long long total = 0;
	int lastIndex = n-1;
	while (true) {
        int min = 1000000001;
        int minIndex = -1;
        for (int i = 0; i < lastIndex; i++) {
            if (min > price[i]) {
                min = price[i];
                minIndex = i;
            }
        }
        long long sumDistance = 0;
        for (int i = minIndex; i < lastIndex; i++) {
            sumDistance += dist[i];
        }
        total += sumDistance * min;
        lastIndex = minIndex;
        if (lastIndex == 0) {
            break;
        }
	}
    cout << total;
}

6개월 후에 다시 풀었을때:
위에서 설명한 그리디 알고리즘을 바탕으로 풀었다
이전 코드와는 다르게 계속 반복해가면서 최소를 찾는 것이 아니라 index와 최소의 cost 를 기록하기 위해서 Pair를 사용해서 풀었다.

import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       Scanner scanner=new Scanner(System.in);
       int n= scanner.nextInt();
       int distance[]=new int[n];
       Pair pair[]=new Pair[n+1];
       for(int i=1;i<=n-1;i++){
           distance[i]= scanner.nextInt();
       }
       for(int i=1;i<=n;i++){
           int cost= scanner.nextInt();
          pair[i]=new Pair(i,cost);
       }
       Arrays.sort(pair,1,n);
       int prevIndex=n;
       long sum=0;
       for(int i=1;i<=n-1;i++){
           if(prevIndex>pair[i].index){
               int indexDiff=prevIndex-pair[i].index;
               long tmpDistance=0;
               for(int j=prevIndex-1;j>prevIndex-1-indexDiff;j--){
                   tmpDistance+=distance[j];
               }
               sum=sum+tmpDistance*pair[i].cost;
               prevIndex=pair[i].index;
           }
       }
        System.out.println(sum);

    }
    public static class Pair implements Comparable{
        private int index;
        private int cost;
        public Pair(int index,int cost){
            this.index=index;
            this.cost=cost;
        }

        @Override
        public int compareTo(Object o) {
            if(o instanceof Pair){
                Pair p=(Pair)o;
                if(this.cost<p.cost){
                    return -1;
                }
                else if(this.cost==p.cost){
                    return 0;
                }
                else{
                    return 1;
                }
            }
            else{
                return -1;
            }

        }
    }


}