백준 1049[자바] java 기타줄
문제 링크: https://www.acmicpc.net/problem/1049
1049번: 기타줄
첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주
www.acmicpc.net
▶문제
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);
}
}
'Alogorithm > 그리디' 카테고리의 다른 글
백준 2212 [자바] java 센서 (0) | 2022.02.17 |
---|---|
백준 13164 [자바] java 행복 유치원 (0) | 2022.02.04 |
백준 11000 [자바] java 강의실 배정 (0) | 2022.01.05 |
[백준] JAVA 21758번 꿀 따기 (0) | 2022.01.02 |
백준 JAVA 21314번 민겸수 (0) | 2021.12.28 |
댓글
이 글 공유하기
다른 글
-
백준 2212 [자바] java 센서
백준 2212 [자바] java 센서
2022.02.17 -
백준 13164 [자바] java 행복 유치원
백준 13164 [자바] java 행복 유치원
2022.02.04 -
백준 11000 [자바] java 강의실 배정
백준 11000 [자바] java 강의실 배정
2022.01.05 -
[백준] JAVA 21758번 꿀 따기
[백준] JAVA 21758번 꿀 따기
2022.01.02