[백준] 12540번 Investing at the Market (Large) C++ 코드

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    int caseNum = 1;

    while (n--) {
        int money;
        cin >> money;

        vector<int> prices(13); // 1-based indexing for prices
        for (int i = 1; i <= 12; ++i) {
            cin >> prices[i];
        }

        int maxProfit = 0; // 최대 이익
        int bestBuy = 0, bestSell = 0; // 최적의 구매/판매 월
        bool found = false; // 유효한 결과가 있는지 여부

        for (int i = 1; i <= 11; ++i) { // 구매 월
            int units = money / prices[i]; // 구매 가능한 상품의 개수
            for (int j = i + 1; j <= 12; ++j) { // 판매 월
                int profit = units * (prices[j] - prices[i]); // 이익 계산

                // 조건 1: 더 높은 이익이 있다면 갱신
                // 조건 2: 같은 이익이라면 더 낮은 구매 가격을 우선 선택
                if (profit > maxProfit || 
                    (profit == maxProfit && prices[i] < prices[bestBuy])) {
                    maxProfit = profit;
                    bestBuy = i;
                    bestSell = j;
                    found = true;
                }
            }
        }

        if (found) {
            cout << "Case #" << caseNum++ << ": " 
                 << bestBuy << " " << bestSell << " " << maxProfit << '\n';
        } else {
            cout << "Case #" << caseNum++ << ": IMPOSSIBLE\n";
        }
    }

    return 0;
}

풀이

문제에 있는 그대로 구현하면 쉽게 해결할 수 있다. 다만 주의할 점은 조건이 2개라는 점. 더 높은 이익이 있다면 갱신하되, 이익이 같다면 더 낮은 구매 가격을 채택해야한다.