16917 양념 반 후라이드 반

먼저 문제 정의부터 했다. 

그리구 어렵다.. 어떻게 손을 대야할지 모르겠었음

 

일단 경우를 나눠서 생각하기로 했다. 치킨은 세 종류가 있으니 총 경우의 수가 6개가 나온다. 먼저 반반이 가장 싼 경우인데 이러면 반반을 가장 많이 사는게 이득이라 최대한 반반으로 사고 남은 닭을 양념이나 후라이드로 채워 넣는다. 

 

다음으로 반반이 가장 비싼 경우이다. 이때는 반반을 버리고 그냥 양념 & 후라이드로 개수를 채운다. 

 

반반 가격이 중간에 있을 때가 제일 애매했다. 일차 함수로 비교를 해야하나 싶었는데 어려워서 말았다. 그래서 이 경우도 다시 반반과 양념+후라, 두개의 단가를 비교해서 위의 경우처럼 나눌 수 있지 않을까 생각했다. 보니깐 처음부터 양념+후라 랑 반반의 단가를 비교해서 계산하면 좋다고 생각했다. 

 

 

알고리즘은 위와 같이 짜서 아래처럼 코딩했다.

#include <iostream>

int main() {
    int a, b, c, x, y;
    scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);
    
    if((a + b) > 2*c){
        if(x > y)
            printf("%d", y*2*c + (x - y)*a);
        else
            printf("%d", x*2*c + (y - x)*b);
    }
    else
        printf("%d", a*x + b*y);
    
    return 0;
}

이상하다.. 예제 3개 중 2개는 맞는데 마지막 하나가 값이 다르게 나온다. 

 

이렇게 나왔다. 실제로는 100000000 이 맞다. 

혹시나 잘못 계산했나 싶어서 중간중간 출력봤지만 오류는 없었다.. 또 혹시나 해서 long long으로도 했지만 똑같았다..(이게 문제였다면 쓰레기 값이 나왔을 것이다) 그렇다.. 로직이 잘못됐다.. 내 생각에는 최대한 반반으로 계산하고 남은 걸 계산해서 더했는데, 여기서 남은 걸 계산해서 더한게 값이 더 클 수도 있다는 생각이 들었다. 피하려 했지만 결국 부등식으로 풀어야겠다.. 

 

당 떨어져서 뭐 좀 먹고 다시 생각해봐야지 -> 이틀동안 생각해봤는데 그래도 어떻게 식을 세울지 모르겠다. hELp.,.

 

---

세개의 값을 동시에 생각하기에는 어려우니깐 case를 나눠서 생각해본다. 반반치킨을 0개 샀을 때 1개 샀을 떄.. 이런식으로 나눠서 최솟값을 구해봤다. 전에 연세대 사탕 나눠주는 문제처럼 하나를 기준잡아서 그 안에 얼마가 드는지 알아보자!

 

반반치킨을 k마리 샀을 때 드는 비용은 위의 식과 같다. 이렇게 반반을 0마리.. 2마리.. 4마리.. 샀을때 값 중 최소를 구해보면 나올 것 같다. 

 

식은 이렇게 세울 수 있다. i를 반반치킨의 개수로 잡았다. 

 

다음으로 종료조건을 생각해봤다. X가 7마리, Y가 12마리 일 때 반반을 가장 많이 사는 경우는 14마리까지 살 수 있다. 그러니깐 최대 x, y중 작은 수까지 살 수 있다.. 그래서 종료조건을 위와 같이 잡았다. 

 

간단하게 작성하면 이렇다. 먼저 최소값에 반반이 0마리 인 경우를 넣어두고 다음부터 개수를 늘려가며 비교한다. 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a, b, c, x, y;
    scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);
    
    int m = a*x + b*y;

    for(int i = 2; (i/2) <= min(x, y); i += 2){ //반반 i마리 구매
        m = min(c*i + a*(x-(i/2)) + b*(y-(i/2)), m);
    }
    printf("%d", m);
}

코드는 이렇게 짰다. 

 

답은 100000000이다

그런데 또 틀렸다!! 그래도 예제에서 막혀서 다행이다. 아니었으면 정답률 막 내려가서 맘 상했을거다. 

 

결국 알게됐다.. 치킨을 버려도 된다. 양념 3마리랑 후라이 5마리를 사야하는데 양념이 만원이고 후라이가 이만원인데 반반이 천원이면 반반 10마리 시켜도 된다. 음.. 그냥.. 그렇다.. 그냥.. 좀.. 어.. 음.. 아깝다

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a, b, c, x, y;
    scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);
    
    int m = a*x + b*y;

    for(int i = 2; (i/2) <= max(x, y); i += 2)
        m = min(c*i + a*(max(0, x-i/2)) + b*(max(0, y-i/2)), m);
    
    printf("%d", m);
}

아무튼 해결했다. max로 최대까지 비교했고 음수 나오면 안 되니 max(0, )으로 음수 막았다. 

 

드디어 맞았네 으휴 다시는 보지말자