[백준] 1049. 기타줄

문제 링크

[백준] 1049. 기타줄

풀이 과정

수학 문제입니다. N개의 기타줄은 최소 금액으로 구매해야 하므로, 다음과 같이 세 개의 방법 중 하나로 구할 수 있습니다.

1. 낱개로만 구매
2. 세트 + 낱개로 구매
3. 세트로만 구매

for (int i = 0; i < M; i++) {
    Pair p = new Pair(sc.nextInt(), sc.nextInt());
    eachIncreasing.add(p);
    setIncreasing.add(p);
}

eachIncreasing.sort((p1, p2) -> p1.each - p2.each);
setIncreasing.sort((p1, p2) -> p1.set - p2.set);

위와 같이 동작하기 위해, 세트와 낱개 각각을 기준으로 리스트에 담아준 뒤 정렬합니다.

int minEach = eachIncreasing.get(0).each;
int minSet = setIncreasing.get(0).set;

answer = Math.min(answer, minEach * N);
answer = Math.min(answer, minSet * (N / 6) + minEach * (N % 6));
answer = Math.min(answer, minSet * (N / 6 + 1));

낱개 가격 중 가장 적은 가격을 minEach로, 세트 가격 중 가장 적은 가격을 minSet에 담아줍니다. 이제 answer에 아래 세 개의 금액 중 최소 값을 담아줍니다.

• 최소 낱개 가격으로 N개를 구매할 때의 금액
• 최소 세트 가격으로 (N / 6)개를 구매한 뒤, 나머지를 최소 낱개 가격으로 구매할 때의 금액
• 최소 세트 가격으로 (N / 6 + 1)개를 구매할 때의 금액

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        ArrayList<Pair> eachIncreasing = new ArrayList<>();
        ArrayList<Pair> setIncreasing = new ArrayList<>();
        int answer = Integer.MAX_VALUE;

        for (int i = 0; i < M; i++) {
            Pair p = new Pair(sc.nextInt(), sc.nextInt());
            eachIncreasing.add(p);
            setIncreasing.add(p);
        }

        eachIncreasing.sort((p1, p2) -> p1.each - p2.each);
        setIncreasing.sort((p1, p2) -> p1.set - p2.set);

        int minEach = eachIncreasing.get(0).each;
        int minSet = setIncreasing.get(0).set;

        answer = Math.min(answer, minEach * N);
        answer = Math.min(answer, minSet * (N / 6) + minEach * (N % 6));
        answer = Math.min(answer, minSet * (N / 6 + 1));

        System.out.println(answer);
    }

    static class Pair {
        int set, each;

        public Pair(int set, int each) {
            this.set = set;
            this.each = each;
        }
    }
}