15. 8980번 택배

8980번: 택배

그리디 알고리즘을 이용하는 문제임

접근하는 방법은 알았는데 구현이 어려웠다.

 

받는 마을 기준으로 오름차순으로 입력받는 주문리스트를 정리한다 (가장 가까운 순서대로)

거기서 가까운 도착할 마을 순서대로 박스를 많이 담아둔다. (가장 가까운 도착마을 것을 가장 많이!)

 

다음 출발 마을에 도착했을 때 

수용량이 박스양보다 많다면 그냥 담고

적다면 남은 수용량 만큼만 담는다

 

수용량만큼 값을 더한게 답

인데 처음에 짠 코드는 3%만에 틀려버림

이거저거 다시 고쳐보니깐 스택오버플로우 나옴 우왕

 

대단히 잘못된 것을 깨닫고 구글갓의 힘을 빌림

 

가장 가까운 도착마을 순서대로 오름차순으로 정리하는 건 맞았는데 구현이 틀린거였음

이분 코드 참고해서 다시 작성함..

[BOJ] 백준 8980번 : 택배 (JAVA)

마을마다 최대 수용량을 정해두고

반복문을 실행하면서 최대로 담을 수 있는 수용량을 구해줌

최대한도 수용량에서 주문마다 담을 수 있는 택배량을 빼줌

다시 최대로 담을 수 있는 수용량을 구해줌 -> 처음에 입력받은 주문양만큼 반복

 

thenby는 왜 됐다 안됐다 하는지 모르겠다

 

using System;
using System.Collections.Generic;
using System.Linq;

namespace _8980
{
    public class Order
    {
        public int start;
        public int end;
        public int amount;

        public Order(int start, int end, int amount)
        {
            this.start = start;
            this.end = end;
            this.amount = amount;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<Order> orderList = new List<Order>();

            string[] input1 = Console.ReadLine().Split(' ');
            int N = int.Parse(input1[0]);
            int C = int.Parse(input1[1]);

            string input2 = Console.ReadLine();
            int M = int.Parse(input2);

            int start, end, amount = 0;

            for (int i = 0; i < M; i++)
            {
                string[] input3 = Console.ReadLine().Split(' ');
                start = int.Parse(input3[0]);
                end = int.Parse(input3[1]);
                amount = int.Parse(input3[2]);

                Order order = new Order(start, end, amount);
                orderList.Add(order);
            }

            var orderd = orderList.OrderBy(x => x.end).ThenBy(x => x.start).ToList();
            //ThenBy 왜 안먹힘

            int result = 0; //답
            //각 마을당 보낼 수 있는 최대 량
            int[] arrCapacity = new int[N+1];
            for(int i=1; i<N; i++)
            {
                arrCapacity[i] = C;
                Console.WriteLine("i: {0}, arrCapacity: {1}",i, arrCapacity[i]);
            }

            Console.WriteLine();

            for (int i = 1; i <= M; i++)
            {
                Order order = orderd[i-1];
                Console.WriteLine("보내는 마을: {0}, 받는 마을: {1}, 보내는 양: {2}",order.start,order.end,order.amount);

                int maxBoxNum = 10000;  //매번 최대값을 넣어줌

                for (int j=order.start; j<order.end; j++)
                {
                    maxBoxNum = Math.Min(maxBoxNum, arrCapacity[j]);
                    Console.WriteLine("j: {0}, arrCapacity[j]: {1}", j, arrCapacity[j]);
                    Console.WriteLine("maxBoxNum: {0}", maxBoxNum);
                }

                if(maxBoxNum>=order.amount)
                {
                    for(int j=order.start; j<order.end; j++)
                    {
                        arrCapacity[j] -= order.amount;
                        
                    }
                    result += order.amount;
                    Console.WriteLine("[여유로움] result: {0}\n",result);
                }
                else
                {
                    for(int j=order.start; j<order.end; j++)
                    {
                        arrCapacity[j] -= maxBoxNum;
                    }
                    result += maxBoxNum;
                    Console.WriteLine("[여유없음] result: {0}\n", result);

                }

            }
                Console.WriteLine(result);
        }
    }
}