백준 No.1049 기타줄 - JAVA

문제

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

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

 

4 2
12 3
15 4

어려웠던 점

처음에 두개의 값이 주어지기 때문에 2차원 배열로 접근했다. new int[M][2] 이렇게 접근했는데 문제를 풀 수 없었다... 둘 다 최소일 수가 없었다.....

 

풀이

-  두 값 패키지와 낱개로 살 때의 배열을 각각 따로 받아 오름차순으로 정렬시킨다. 그러면 0번 인덱스는 제일 작은 값이 된다.

-  그러고 패키지(6개)로 살 때와 낱개로 구매했을 때 중 더 싼 가격을 찾는다. 근데 여기서 중요한게 있었다. 

-   예제 입력이 많은 이유가 있었다. 패키지 두번 사는게 낱개로 사는 거보다 싼 경우가 있다. 예를 들어 15 8 이 주어지고 만약 끊어진 줄이 4개 인 경우 낱개로 사면 가격이 32다. 근데 여기서 패키지로 구매하고 사용할 수도 있다. 오히려 그게 더 싼 경우이다. 그렇기 때문에 ((N/6)+1) * pack[0]  의 식을 구할 수 있다. (6개로 나누고 +1 해야함 끊어진 기타 줄이 1개이면 1/6이 되는데 이런 경우에도 패키지 하나를 사서 하는게 더 나을 수도 있다 .딱 6개인 경우도 그런 경우가 있을 수 있다고 가정)

- 다른 식인 낱개로만 구매할 경우 식을 구하는 식은 (N*single[0]) 이다. 전부 낱개이므로 그냥 곱하면 된다.

- 근데 여기서 패키지를 구매하고 낱개로 몇개 더 구매하는 경우도 있을 수 있으므로 ((N/6) * pack[0] + N*single[0]) 을 구할 수 있다. 여기서는 +1을 하지 않는다. 이 값은 패키지를 사고 다음 값들은 전부 낱개로 구매한다는 가정하에 구한 식이므로 그렇다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   //끊이전 줄 개수
        int M = Integer.parseInt(st.nextToken());   //주어지는 브랜드 개수

        int single[] = new int[M];
        int pack[] = new int[M];


        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());

            pack[i] =  Integer.parseInt(st.nextToken());  //6개
            single[i] = Integer.parseInt(st.nextToken());   //한 개
        }
        //각각 가장 작은 값 찾기
        Arrays.sort(single);
        Arrays.sort(pack);
        int result = 0;
        int temp = Integer.MAX_VALUE;


        //1을 더한 이유는 그 만약 끊엊니게 8개라해도 6개 단위로 두개 사는게 더 쌀 수도 있음

        result = Math.min(((N/6)+1)*pack[0],single[0] * N);
        result = Math.min(result,(N/6)*pack[0]+(N%6)*single[0]);


        System.out.println(result);



    }
}