백준#1049 - 기타줄

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

1049번: 기타줄

그리디 알고리즘으로 분류된 1049번 기타줄 문제 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1049
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] splitInput = Console.ReadLine().Split(' ');
            int needCount = int.Parse(splitInput[0]);
            int brandCount = int.Parse(splitInput[1]);
 
            //최소 패키지 가격과 최소 낱개 가격을 초기화.
            int minPackageCost = int.MaxValue;
            int minPieceCost = int.MaxValue;
 
            for(int i = 0; i < brandCount; i++)
            {
                string[] strSplitCost = Console.ReadLine().Split(' ');
 
                //입력 받은 패키지 값이 최소 패키지 값보다 작을 때.
                if (int.Parse(strSplitCost[0]) < minPackageCost)
                    minPackageCost = int.Parse(strSplitCost[0]);
 
                //낱개 가격이 최소 낱개 가격보다 작을 때.
                if (int.Parse(strSplitCost[1]) < minPieceCost)
                    minPieceCost = int.Parse(strSplitCost[1]);
            }
 
            //낱개 6개의 가격이 패키지 보다 작다면
            if (minPieceCost * 6 <= minPackageCost)
            {
                Console.WriteLine(needCount * minPieceCost);
                return;
            }
 
            //패키지 구매가 이득일 때 까지 구매.
            int usePackageCost = (needCount / 6) * minPackageCost;
            needCount = needCount % 6;
 
            //패키지 구매후 남은 갯수를 패키지로, 낱개로 살지 결정.
            if (needCount * minPieceCost <= minPackageCost)
                Console.WriteLine(usePackageCost + needCount * minPieceCost);
 
            else
                Console.WriteLine(usePackageCost + minPackageCost);
        }
    }
}

 

필요한 기타줄의 갯수, 브랜드의 수와 브랜드에서 판매되는 각각의 패키지, 낱개 가격이 주어

졌을 때 필요한 최소한 금액의 가격을 구하느 문제 입니다. 패키지는 줄 6개로 이루어집니다.

 

ex)

10 3

20 8

40 7

60 4

입력 값이 다음과 같이 주어지며 첫줄이 필요한 기타줄, 브랜드 갯수 이고

다음 줄부터 각 브랜드의  패키지 낱개 가격이 되겠습니다.

 

제가 가장먼저 생각한 이 문제의 접근 모든 브랜드의 패키지와 낱개 가격이 주어지지만

각각의 최소 가격을 제외 하고는 관심이 없다는 것 입니다.

제가 만일 패키지를 구매한다면 가격이 20인 브랜드에서 구매하고 다른 곳은 쳐다도 안볼겁니다.

마찬가지로 낱개를 구매한다면 가격이 4인 브랜드에서 구매할 것입니다.

 

입력을 받을 때부터 최소 가격을 각각 구할겁니다. minPackageCost 와 minPieceCost를

int의 최댓값으로 초기화 하고 입력 받는 족족 최솟값을 넣도록 했습니다.

 

다음으로 낱개 6개의 가격이 패키지 하나의 가격보다 저렴할 수 있습니다. 이 경우

필요한 갯수를 전부 낱개로 구매해 출력하고 종료합니다.

 

아닐 경우 패키지 구매를 반드시 해야 이득이며 패키지를 사서 줄이 남지 않을 때까지

패키지를 구매합니다. 그럼 6의 나머지로 필요한 줄의 갯수가 남게 됩니다.

 

마지막으로 남은 갯수를 패키지로 하나 구매할지 낱개로 갯수를 맞춰 구매할지 결정합니다.

이를 계산하고 결과를 출력하면 되겠습니다.