2025 SCPC 1-2

1
#include <bits/stdc++.h>
2
#define fIO ios_base::sync_with_stdio(false); \
3
cin.tie(NULL);
4
using namespace std;
5

6
// 잔돈 4,500원을 줄 수 있는지 판단하는 함수
7
bool giveChange(int& coin500, int& coin1000)
8
{
9
    int change = 4500;
10

11
    // 큰 단위(1000원)부터 최대한 사용
12
    int use1000 = min(change / 1000, coin1000);
13
    change -= use1000 * 1000;
14
    coin1000 -= use1000;
15

16
    // 나머지를 500원짜리로
17
    int use500 = min(change / 500, coin500);
18
    change -= use500 * 500;
19
    coin500 -= use500;
20

21
    // 잔돈을 줄 수 있으면 true, 아니면 false
22
    if (change == 0) return true;
23

24
    // 실패하면 복구
25
    coin1000 += use1000;
26
    coin500 += use500;
27
    return false;
28
}
29

30
int main()
31
{
32
    fIO
33
    int T; // 테스트 케이스 수
34
    cin >> T;
35

36
    for (int case_num = 1; case_num <= T; ++case_num)
37
    {
38
        int n;
39
        cin >> n;
40
        vector<int> customers(n);
41

42
        for (int i = 0; i < n; ++i)
43
        {
44
            cin >> customers[i];
45
        }
46

47
        int coin500 = 0, coin1000 = 0; // 철수의 보유 금액
48
        int sold = 0;                  // 판매 성공 수
49

50
        for (int i = 0; i < n; ++i)
51
        {
52
            int pay = customers[i];      // 손님이 낸 돈
53

54
            if (pay == 500)
55
            {
56
                coin500++;
57
            }
58
            else if (pay == 1000)        // 손님이 낸 돈이 1000이면
59
            {
60
                if (coin500 >= 1)        // 500동전이 1개 이상일 때 500과 1000 교환
61
                {
62
                    coin500--;
63
                    coin1000++;
64
                } else
65
                {
66
                    break;
67
                }
68
            }
69
            else if (pay == 5000)        // 손님이 낸 돈이 5000이면
70
            {
71
                if (!giveChange(coin500, coin1000))
72
                {
73
                    break;
74
                }
75
            }
76
            sold++;
77
        }
78

79
        cout << "Case #" << case_num << endl << sold << endl;
80
    }
81

82
    return 0;
83
}