코드 포스 (Code Forces) - New Bakery (C++)

 

 

밥은 N개의 빵을 판매할 것이다.

 

밥은 0 <= K <= min(n, b) 범위를 만족하는 K를 하나 고를 것이다.

K개의 빵을 판매할 때, i번째로 판매되는 빵의 가격은 (b - i + 1)원으로 판매할 것이다.

K개의 빵을 모두 판매한 뒤에 남은 빵은 모두 a원의 고정 가격으로 판매할 것이다.

 

이 때, K값에 따라 총 매출은 달라지는데 가능한 경우중 총 매출의 최대값을 구하여 출력하면 된다.

 

문제 풀이

이 문제는 특정할 알고리즘을 사용하기 보단 아이디어를 떠올려 해결하는 문제이다.

두 가지의 경우를 생각해보자.

 

1. b >= a 인 경우

K개의 빵에 대해, 판매되는 빵의 가격은 b원, b - 1원, b - 2원.....b - k + 1원이 된다.

이 때, 이 가격이 모두 a원보다 크거나 같은 값이 되어야 매출은 최대가 될 것이다.

(k가 너무 커서 b - k + 1이 a원보다 작게 되면, a원으로 판매할 때보다 손해를 보기 때문에)

 

즉, b - k + 1 = a 를 만족하는 k에 대해, 총 매출이 최대가 될 것이다.

 

2. b < a 인 경우

이 경우엔, K개의 빵에 대해 모두 a원보다 낮은 가격으로 판매하게 된다.

차라리 모든 빵을 a원으로 판매하는 것이 이득일 것이다.

그러므로, k가 0일 때 총 매출이 최대가 될 것이다.

 

위의 두 경우를 고려하여 답을 구하여 출력하면 된다.

 

풀이 코드

테스트케이스의 수를 입력받는 것은 제외하고 코드를 설명할 것이다.

long long N = 0;
long long A = 0;
long long B = 0;

std::cin >> N >> A >> B;

먼저 값을 입력받아 준다.

long long K = std::max((long long)0, std::min(N, B - A));

K값을 위와 같이 세팅해준다.

 

B가 A보다 크거나 같다면, B - A개만큼 A원보다 크거나 같은 값으로 판매할 수 있다. 반면, B가 A보다 작은 경우엔 1개도 A원보다 비싸게 판매할 수 없다. B가 A보다 작게 되면, B - A가 음수가 되므로 K값은 0이 된다.

 

또한 K의 범위는 0 <= K <= min(n, b) 이므로 B-A가 N보다 큰 경우 N으로 값을 조정해주었다.

long long Answer = GetProfit(K, NumOfBun, BasicPrice, FirstModifiedPrice);

GetProfit이라는 함수는 총 이익을 계산해주는 함수이다. 

long long GetProfit(long long _K, long long _N, long long _A, long long _B)
{
    long long SumProfit = 0;

    SumProfit += _B * (_B + 1) / 2;
    SumProfit -= (_B - _K) * (_B - _K + 1) / 2;
    SumProfit += _A * (_N - _K);

    return SumProfit;
}

등차수열의 합 공식을 사용하여 간단하게 총 이익을 구해주었다.

함수가 반환한 값을 출력해주면 된다.

 

 

코드 전문

#include <iostream>
#include <vector>

long long GetProfit(long long _K, long long _N, long long _A, long long _B)
{
    long long SumProfit = 0;

    SumProfit += _B * (_B + 1) / 2;
    SumProfit -= (_B - _K) * (_B - _K + 1) / 2;
    SumProfit += _A * (_N - _K);

    return SumProfit;
}

int main()
{
    int NumCase = 0;
    std::cin >> NumCase;

    std::vector<long long> Answers(NumCase);

    for (long long Case = 0; Case < NumCase; Case++)
    {
        long long N = 0;
        long long A = 0;
        long long B = 0;

        std::cin >> N >> A >> B;

        long long K = std::max((long long)0, std::min(N, B - A));
        long long Answer = GetProfit(K, N, A, B);

        Answers[Case] = Answer;
    }

    for (int i = 0; i < NumCase; i++)
    {
        std::cout << Answers[i] << "\n";
    }

    return 0;
}