본문 바로가기

공부/알고리즘 문제풀이

[SW Expert Academy] 3347. 올림픽 종목 투표

반응형

3347. 올림픽 종목 투표


SW Expert Academy의 글은 무단 복제가 금지되어 있기 때문에 링크로 대체하겠습니다.

클릭시 이동합니다.


어떻게 풀까?


일단, 올림픽 종목 개최 비용에 대한 배열을 선언하고,

조직 위원회의 상한 비용에 대한 정보를 저장하는 배열을 선언합니다.


그리고, 올림픽 종목을 앞에서부터 살펴가면서, 조직 위원회의 상한 비용보다 작은 올림픽 종목이 나온다면 해당 종목에 투표합니다!


그리고 마지막에 이 투표수가 가장 많은 올림픽 종목을 출력합니다..!

세상에...!


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cstring>
 
int A[2][1001];
int B[1001], n, m;
 
int main(){
    int t;
    scanf("%d\n"&t);
 
    for(int tc = 1; tc <=  t; tc++){
        scanf("%d %d"&n, &m);
        memset(A, 0sizeof(A));
 
        for(int i = 1; i <= n; i++){
            scanf("%d \n"&A[0][i]);
        }
        for(int i = 1; i <= m; i++){
            scanf("%d \n"&B[i]);
        }
 
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++){
                if(A[0][j] <= B[i]) {
                    A[1][j]++;
                    break;
                }
            }
        }
 
        int res[2= {-1,0};
        for(int i = 1; i <= n; i++){
           if(A[1][i] > res[0]) {
                res[0= A[1][i];
                res[1= i;
           }
        }
        printf("#%d %d\n", tc, res[1]);
    }
    return 0;
}
cs


여담



SWEA의 D4 난이도를 모욕하는 문제라고 생각합니다!

D3는 될거 같은데 말이죠..


어쨌든, 시간 복잡도는 O(NM)입니다.

반응형