2025 SCPC 1-1

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main()
5
{
6
    int T;        //테스트 케이스의 갯수
7
    cin >> T;
8
    for (int case_num = 1; case_num <= T; ++case_num)
9
    {
10
        int n;    //손님 수
11
        cin >> n;
12
        vector<int> customers(n);  //손님이 낸 금액
13
        for (int i = 0; i < n; ++i)
14
        {
15
            cin >> customers[i];
16
        }
17

18
        int cnt500 = 0, cnt1000 = 0;      //철수가 가지고 있는 500, 1000의 갯수
19
        int sold = 0;                     //지금까지 판 손님 수
20

21
        for (int i = 0; i < n; ++i)
22
        {
23
            int pay = customers[i];       //손님이 낸 돈
24
            if (pay == 500)               //손님이 낸 돈이 500원이라면
25
            {
26
                cnt500++;                 //cnt500 +1
27
            } else if (pay == 1000)       //손님이 낸 돈이 1000원이라면
28
            {
29
                if (cnt500 >= 1)          //500동전을 1개 이상가졌다면 1000과 교환
30
                {
31
                    cnt500--;
32
                    cnt1000++;
33
                } else break;             //500동전이 없다면 종료
34
            } else if (pay == 5000)       //손님이 5000을 낸다면 -> 잔돈이 4500원 필요
35
            {
36
                if (cnt1000 >= 3 && cnt500 >= 0)
37
                {
38
                    cnt1000 -= 3;
39
                }
40
                else if (cnt1000 >= 2 && cnt500 >= 5)
41
                {
42
                     cnt1000 -= 2;
43
                     cnt500 -= 5;
44
                }
45
                else if (cnt1000 >= 1 && cnt500 >= 7)
46
                {
47
                    cnt1000 -= 1;
48
                    cnt500 -= 7;
49
                }
50
                else if (cnt500 >= 9)
51
                {
52
                    cnt500 -= 9;
53
                }
54
                else
55
                {
56
                    break;  // 잔돈 부족
57
                }
58
            }
59
            sold++;
60
        }
61

62
        cout << "Case #" << case_num << endl << sold << endl;
63
    }
64
    return 0;
65
}