[알고리즘 문제] 백준1049 - 기타줄

문제는 여러개의 브랜드에서 최소의 가격으로 원하는 만큼의 기타줄을 사는 문제이다.

 

먼저 각 브랜드마다 기타줄을 6개 세트 가격, 낱개의 가격으로 판매한다. 세트의 가격, 낱개의 가격을 입력받으면서 각각 최소값을 구한다. 

이 최소값을 사용하여 6개를 사는데 세트의 가격과 낱개 * 6의 가격을 비교한다. 만약 세트인 경우가 더 싸면 N/6개를 구매하고, 더 비싸면 N/6*6개를 구매한다. 그리고 구매한 만큼 N개에서 빼준다(6으로 나누었을 때 나머지 값)

 

이렇게 하는 이유는, 만약 필요한 기타줄이 33개인 경우 30개까지 사는데 더 싸게 사기 위함이다. 

 

다시 남은 N개를 가장 싸게 사는 경우를 생각한다. 한 세트를 사는 경우와 N*1개의 가격중 더 싼 가격을 선택하며 money에 더해준다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] units = new int[M];
        int[] brands = new int[M];

        int unitMin = 987654321;
        int brandMin = 987654321;

        for (int i = 0; i < M; i++) {
            brands[i] = sc.nextInt();
            units[i] = sc.nextInt();

            if (units[i] < unitMin) {
                unitMin = units[i];
            }

            if (brands[i] < brandMin) {
                brandMin = brands[i];
            }
        }

        int money = 0;

        if (brandMin < unitMin * 6) {
            money += (N / 6) * brandMin;
        } else {
            money += unitMin * (N / 6) * 6;
        }

        N %= 6;

        if (brandMin < (N * unitMin)) {
            money += brandMin;
        } else {
            money += (N * unitMin);
        }

        System.out.println(money);
    }
}

for문에서는 낱개의 최저가격, 세트의 최저가격을 구한다.

 

그리고 첫번째 if문에서 6의 배수개까지의 최소 가격을 구한다. 33개가 필요한 경우라면, 30개까지 구매하는데 최소 가격을 구한다.

 

그리고 N에 N을6으로 나누었을 때 나머지 값을 다시 넣어주는데, 이는 30개까지 구매했으니 나머지 3개를 구매하는데 최소 가격을 알기 위해서 이다.

 

마지막으로 나머지를 구매하는데 최소비용을 구한다.