[C++] 백준 9419번 - 프로그래밍 대회 전용 부지 - 정렬, 지수 연산 (sort, pow)

 

🔍  문제 요약

문제 링크: 백준 9419 - 프로그래밍 대회 전용 부지

상근이의 목표
상근이는 해마다 땅을 하나씩 사면서, 모든 땅을 최소 비용으로 사들이려 한다.
1년이 지날 때마다 땅값은 두 배로 상승하므로, 더 비싼 땅일수록 먼저 사야 전체 비용이 줄어든다.

• 조건
  • 매년 1개 땅만 구입 가능 (1년 후부터)
  • 가격은 2 × L × t^t로 증가 (L은 땅값, t는 구매한 해의 번호)
  • 총 보유 금액: 5,000,000 억원
• 목표: 주어진 테스트 케이스마다 땅을 모두 구입할 수 있는지, 최소 비용을 출력한다.

---

💡 문제 분석

• 가격은 매년 기하급수적으로 증가하기 때문에, 비싼 땅부터 먼저 구매해야 최적의 해법
• 각 테스트 케이스는 0으로 끝나며, 최대 40개의 땅 → O(n log n) 정렬 후 계산 가능
• 단위가 억이고, 총 예산은 5천만 억 → 64비트 정수(long long) 사용 필요
• 최대값 초과 시 "Too expensive" 출력

---

🔑 핵심 아이디어

• 정렬 (내림차순): 가장 비싼 땅을 먼저 사야 비용이 줄어든다.
• 계산식 적용: cost = 2 × L × (2^t) (t: 구매한 해의 번호)
• 누적 비용이 5,000,000을 넘으면 실패 처리

---

🧩 풀이 전략

1. 테스트 케이스마다 땅 가격을 저장 (벡터 활용)
2. 내림차순 정렬
3. 연차(t) 별로 땅 구매 비용 계산 및 누적
4. 누적 총합이 5,000,000 이하이면 출력, 초과 시 "Too expensive" 출력

---

🧪 예제 입출력

입력:
3
7
2
10
0
20
29
31
0
42
41
40
37
20
0

출력:
134
17744
Too expensive

 

---

🖥️ 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const long long MAX_MONEY = 5000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--) {
        vector<int> lands;
        while (true) {
            int val;
            cin >> val;
            if (val == 0) break;
            lands.push_back(val);
        }

        sort(lands.begin(), lands.end(), greater<int>());

        long long total = 0;
        bool expensive = false;
        for (int i = 0; i < lands.size(); i++) {
            long long price = lands[i] * (1LL << (i + 1));
            total += price;
            if (total > MAX_MONEY) {
                expensive = true;
                break;
            }
        }

        if (expensive) cout << "Too expensive\n";
        else cout << total << "\n";
    }

    return 0;
}

---

⏱️ 시간복잡도 분석

단계	시간 복잡도
정렬	O(N log N)
계산	O(N)
테스트케이스 T개	T × O(N log N)
👉 최대	10 × 40 log 40 → 매우 빠름

 

---

✨ 정리

• 핵심은 기하급수적 땅값 상승 → 비싼 땅을 먼저 사는 전략이 최적
• 정렬 후 순차 구매 전략으로 깔끔하게 해결 가능
• 숫자 단위(억)에 주의하기
• 오버플로우 방지를 위해 long long 사용하기