오늘 풀어볼 문제는 백준 16917번 문제 "양념 반 후라이드 반" 이다.
이 문제는 브론즈2 문제이고 브루트 포스 문제이다.
문제
현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다.
반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다.
양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원이다.
상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다.
반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다.
상도가 치킨을 구매하는 금액의 최솟값을 구해보자.입력
첫째 줄에 다섯 정수 A, B, C, X, Y가 주어진다.출력
양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최솟값을 출력한다.📌첫 번째 시도📌
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] array = new int[5];
int sum = 0;
for(int i=0; i<array.length; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
while(array[3]>0 || array[4]>0) {
if ((array[0] + array[1] > 2 * array[2]) && (array[3] >= 1) && (array[4] >= 1)) {
int count_C = Math.min(array[3], array[4]);
sum = sum + array[2] * 2 * count_C;
array[3] = array[3] - count_C;
array[4] = array[4] - count_C;
System.out.println("sum1 = " + sum);
}
else {
if(array[3] != 0) {
sum = sum + array[0] * array[3];
array[3] = 0;
System.out.println("sum3 = " + sum);
}
if(array[4] != 0) {
sum = sum + array[1] * array[4];
array[4] = 0;
System.out.println("sum4 = " + sum);
}
}
}
System.out.println(sum);
}
}첫 번째 시도의 코드이다.
"양념 + 후라이드" 랑 "반반" * 2 랑 비교했을 때 어떤 방식으로 구매를 해야 더 싸게 살 수 있는지 결론이 나온다.
그렇게 if문으로 비교를 해서 그 방식대로 쭉 구매하는 방향으로 코드를 짰는데 문제에서 제공한 3번째 예제에서 답이 계속 다르게 나왔다.
어디가 문제인지 계속 알아보다가 문제에서 "최소"로 구매를 했다는 사실을 못 읽었다..
결국 최소 마리에서 더 사도 상관 없다는 것을 깨우쳤다..
그럼 코드를 다시 짜보겠다.
📌두 번째 시도📌
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] array = new int[5];
int sum = 0;
for(int i=0; i<array.length; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
while(array[3]>0 || array[4]>0) { // 후라이드 개수와 양념 개수가 모두 0 마리 이하가 될 때까지 반복한다.
if ((array[0] + array[1] >= 2 * array[2]) && (array[3] >= 1) && (array[4] >= 1)) { // 후 + 양 > 2 * 반반이고 각각 한 마리 이상 있을 때,
int count_C = Math.min(array[3], array[4]); // 후라이드와 양념 중 최소 개수를 각가에 빼준다.
sum = sum + array[2] * 2 * count_C;
array[3] = array[3] - count_C;
array[4] = array[4] - count_C;
// System.out.println("sum1 = " + sum);
}
else { // 후 + 양 < 2 * 반반 일 때,
if(array[0] > 2 * array[2] && array[3] >= 1) { // 후 > 2 * 반반 일 때,
int count_C = Math.abs(array[3] - array[4]);
sum = sum + array[2] * count_C * 2;
// array[3] = array[3] - count_C;
// System.out.println("sum2 = " + sum);
} else {
if(array[3] != 0) {
sum = sum + array[0] * array[3];
array[3] = 0;
// System.out.println("sum3 = " + sum);
}
}
if(array[1] > 2 * array[2] && array[4] >= 1) { // 양 > 2 * 반반 일 때,
int count_C = Math.abs(array[3] - array[4]);
sum = sum + array[2] * count_C * 2;
array[4] = array[4] - count_C;
// System.out.println("sum4 = " + sum);
} else {
if(array[4] != 0) {
sum = sum + array[1] * array[4];
array[4] = 0;
// System.out.println("sum5 = " + sum);
}
}
}
}
System.out.println(sum);
}
}정말 열심히.. 머리를 쥐어짜며 if문을 무작위하게 넣어서 예제 3번을 통과시켰는데.. 백준에 등록하니깐 시간초과가 떴다... 무한루프가 돌고 있는건가..? 어디가 문제일까..🥹
📌세 번째 시도📌
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 A = Integer.parseInt(st.nextToken()); // 후라이드 치킨 가격
int B = Integer.parseInt(st.nextToken()); // 양념 치킨 가격
int C = Integer.parseInt(st.nextToken()); // 반반 치킨 가격
int X = Integer.parseInt(st.nextToken()); // 후라이드 치킨 수량
int Y = Integer.parseInt(st.nextToken()); // 양념 치킨 수량
int sum = 0;
while(X > 0 || Y > 0) { // 후라이드 개수와 양념 개수가 모두 0 마리 이하가 될 때까지 반복한다.
if ((A + B >= 2 * C) && (X >= 1) && (Y >= 1)) { // 후 + 양 >= 2 * 반반이고 각각 한 마리 이상 있을 때,
int count_C = Math.min(X, Y); // 후라이드와 양념 중 최소 개수를 각가에 빼준다.
sum = sum + C * 2 * count_C;
X = X - count_C;
Y = Y - count_C;
// System.out.println("sum1 = " + sum);
}
else { // 후 + 양 < 2 * 반반 일 때,
if(A >= 2 * C && X >= 1) { // 후 >= 2 * 반반 일 때,
sum = sum + C * X * 2;
X = 0;
// array[3] = array[3] - count_C;
// System.out.println("sum2 = " + sum);
} else {
if(X != 0) {
sum = sum + A * X;
X = 0;
// System.out.println("sum3 = " + sum);
}
}
if(B >= 2 * C && Y >= 1) { // 양 >= 2 * 반반 일 때,
int count_C = Y;
sum = sum + C * count_C * 2;
Y = 0;
// System.out.println("sum4 = " + sum);
} else {
if(Y != 0) {
sum = sum + B * Y;
Y = 0;
// System.out.println("sum5 = " + sum);
}
}
}
}
System.out.println(sum);
}
}틀린 부분은 아마 내가 코드를 쥐어짜다보니 중복된 계산을 계속하고 있어서 시간초과가 난 것 같다.
결국 성공했고,, 런타임 시간이 조금 맘에 안들지만.. ㅎㅎ 여기서 더이상 최적화를 못 하겠다..🥹
눈물겨운 나의... 시간 초과 ㅎㅎ
성공했다 그래도 헤헤
💻 💻 💻