[Baekjoon] 1049번: 기타줄
2023. 3. 30. 21:26ㆍComputer Sciences/Problem Solve
https://www.acmicpc.net/problem/1049
문제 설명
새로운 기타줄을 사기 위한 가능한 적은 돈을 구해야 한다.
끊어진 기타줄 개수 N개와 브랜드 M개가 주어지고, 각 브랜드에서 파는 기타줄 6개 묶음의 패키지와 낱개로 살 때 가격이 주어진다.
풀이 방법
단순한 그리디 문제이다.
먼저 오름차순 정렬을 하여 패키지에서 최솟값과 낱개의 최솟값을 구한다.
그 다음 패키지로만 샀을 때와 낱개로만 샀을 때의 가격을 비교하여 적은 값을 구한다.
그 다음 패키지와 낱개를 함께 샀을 때의 가격을 위 가격과 비교하여 최솟값을 구한 뒤 최솟값을 출력하면 된다.
import java.io.*;
import java.util.Arrays;
class Main {
static final int stringsCount = 6;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int N = Integer.parseInt(split[0]);
int M = Integer.parseInt(split[1]);
int MIN = Integer.MAX_VALUE;
int[] packages = new int[M];
int[] pieces = new int[M];
for (int i = 0; i < M; i++) {
split = br.readLine().split(" ");
packages[i] = Integer.parseInt(split[0]);
pieces[i] = Integer.parseInt(split[1]);
}
Arrays.sort(packages);
Arrays.sort(pieces);
MIN = Math.min(((N / stringsCount) + 1) * packages[0], N * pieces[0]);
MIN = Math.min(MIN, ((N / stringsCount)) * packages[0] + (N % stringsCount) * pieces[0]);
System.out.print(MIN);
}
}
'Computer Sciences > Problem Solve' 카테고리의 다른 글
[Baekjoon] 3273번: 두 수의 합 (0) | 2023.04.03 |
---|---|
[Baekjoon] 1463번: 1로 만들기 (0) | 2023.03.31 |
[Baekjoon] 2467번: 용액 (0) | 2023.03.29 |
[Baekjoon] 1806번: 부분합 (0) | 2023.03.28 |
[Baekjoon] 6198번: 옥상 정원 꾸미기 (0) | 2023.03.27 |