백준 1049[자바] java 기타줄

문제 링크: https://www.acmicpc.net/problem/1049

1049번: 기타줄

▶문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타 줄의 개수 N과 기타 줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타 줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

▶입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

▶출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

▶해설

문제는 그리디 알고리즘으로 해결할 수 있습니다. 조건을 살펴보겠습니다.

 

1. 기타줄은 1개 혹은 6개의 세트로 샀을 때 가격이 주어진다. 

2. 기타줄은 적어도 N개를 사기 위함이므로 N개 이상을 사도 무방하다. 

 

현재 입력이 여러 개 주어지지만 저희는 1개 혹은 세트로 살 때 가장 저렴한 가격이 필요합니다. 

1. 1개를 샀을 때 가장 저렴한 가격

2. 6개를 샀을 때 가장 저렴한 가격

 

이때 1개 가격으로 6개 샀을 때 더 저렴하다면 1개의 가격*N으로 출력하면 끝입니다.

result = oneArr[0] * n;

 

하지만 6개 샀을 때가 더 저렴하다면 나머지와 몫을 이용해서 구합니다. 

1. N을 6으로 나눴을 때 나머지가 없다면 (N/6 * 세트 가격) 그대로 사는 것이 가장 저렴합니다.  

2. N을 6으로 나눴을 때 나머지가 존재한다면 나머지 *1개의 가격 VS 세트 가격을 비교합니다. 

rest = n % 6;
if (rest==0) {
    result = sixArr[0] * (n / 6);
}
else {
    if (rest * oneArr[0] > sixArr[0]) {
        result = sixArr[0] * (n / 6 + 1);
    }
    else {
        result = sixArr[0]*(n/6)+rest*oneArr[0];
    }
}

 

전체 코드 

import java.io.*;
import java.util.*;
import java.lang.*;


public class Main {

    static int n, m;
    static int[] oneArr;
    static int[] sixArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);


        oneArr = new int[m];
        sixArr = new int[m];

        for (int i = 0; i < m; i++) {
            String[] s1 = br.readLine().split(" ");
            sixArr[i] = Integer.parseInt(s1[0]);
            oneArr[i] = Integer.parseInt(s1[1]);
        }

        Arrays.sort(oneArr);
        Arrays.sort(sixArr);

        int result = 0;

        int rest = 0;
        if (oneArr[0] * 6 >= sixArr[0]) {
            rest = n % 6;
            if (rest==0) {
                result = sixArr[0] * (n / 6);
            }
            else {
                if (rest * oneArr[0] > sixArr[0]) {
                    result = sixArr[0] * (n / 6 + 1);
                }
                else {
                    result = sixArr[0]*(n/6)+rest*oneArr[0];
                }
            }
        } else {
            result = oneArr[0] * n;
        }

        System.out.println(result);

    }
}