C# 13305번 주유소

문제

58점 받은 코드

using System;
using System.Linq;
using System.Numerics;

namespace _5
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());

            int[] d = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int[] won = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            won[won.Length-1] = 1000000000;

            int minWon = 0;
            int minWonIndex = 0;
            BigInteger output = new BigInteger();
            int limitD = d.Length;
            BigInteger checkD = new BigInteger();
            BigInteger sumD = new BigInteger();
            foreach (var item in d)
            {
                sumD += BigInteger.Parse(item.ToString());
            }

            while(sumD > checkD)
            {
                minWon = won.Min();
                minWonIndex = Array.IndexOf(won, minWon);

                for (int i = minWonIndex; i < limitD; i++)
                {
                    
                    output += BigInteger.Parse(minWon.ToString()) * BigInteger.Parse(d[i].ToString());
                    checkD += BigInteger.Parse(d[i].ToString());
                    won[i] = 1000000000;
                }
                limitD = minWonIndex;
            }

            Console.WriteLine(output.ToString());
        }
    }
}

주유가격이 가장 작은 값을 찾고 이후의 모든 거리를 해당 주유가격으로 곱하고 그 거리에 대해서 다시 최소값을 찾고 이후 거리를 해당 주유가격으로 곱하는 식으로 풀었다. 100점이 안나오는 이유를 알아보니 시간복잡도의 문제가 있음을 알게 되었다. 이중포문을 쓰지 않는 방식을 연구했다.

100점 받은 코드

using System;
using System.Linq;
using System.Numerics;
using System.Text;

namespace _5
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            long[] d = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            long[] won = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);

            //최소 주유 가격
            long minWon = won[0];
            //결과
            long output = 0;                     

            for (int i = 0; i < d.Length; i++)
            {
                if(minWon < won[i])
                {
                    output += minWon * d[i];
                }
                else
                {
                    output +=won[i] * d[i];
                    minWon = won[i];
                }
            }         
            Console.WriteLine(output);
        }
    }
}

첫 장소에 해당하는 주유가격과 거리를 바로 곱했다. 이후 장소마다 바로바로 주유가격과 거리를 곱해서 넘겨주었다. 

단, 해당 장소의 주유가격이 이전 장소의 주유가격보다 비쌀 경우 이전 주유가격으로 곱하여 해당 장소에서는 주유하지 않는 방식으로 했다. 

이렇게 했더니 시간복잡도가 O(n)가 되어 풀렸다.