Suhwanc

아마 이 문제 때문에 찾아오신 분들은 시간 초과 때문에 화가 나서 검색해 들어오셨을 텐데

문제 풀이는 생략하고 시간을 줄이는 방법에 대해 설명하겠습니다.ㅠㅠ

 

  • 우선, class를 만들어 vector로 저장하든, 그냥 각각을 배열로 저장하든, 큰 차이는 없어 보입니다. (물론, vector가 조금 더 느리긴 하나, 깔끔하게 구현된 vector는 정답이 가능합니다)
  • c++의 경우, cin, cout을 마구 쓰면 참가자의 정보(0과 1)를 저장할 때 최대 400만 번 입력을 받아야하기 때문에 무조건 시간초과입니다. 
  • 하지만 printf, scanf를 써도 400만번 입력은 2초 안에 정답을 낼 수 없습니다. 
  • 그렇기 때문에 cin.tie(0), sync_with_stdio(false)를 쓴 후 cin, cout을 사용해도 시간 초과입니다.
  • 따라서, 최대 400만 번 입력을 받는 곳을 getchar()로 받아주셔야 합니다. (어차피 0과 1만 입력되기 때문)
  • 추가로, getchar()를 사용하면 입력 버퍼에 "\n" 이 남기 때문에 뒤에 getchar()를 한 번 더 사용해주어야 합니다.

이 방법을 적용한 코드는 아래와 같습니다.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
 
bool check[2001][2001];
int p_score[2001];
int score[2001]; //문제 배점 배열
int num[2001]; //사람 당 푼 문제 수 배열
int main()
{
    int t; scanf("%d"&t);
    int cnt = 0;
    while (t--) {
        cnt++;
        printf("#%d ", cnt);
        int N, T, P; 
        scanf("%d %d %d"&N, &T, &P);  
        getchar();
        memset(score, 0sizeof(score));
        memset(num, 0sizeof(num));
        memset(check, falsesizeof(check));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= T; j++) {
                char ch = getchar();
                getchar();
                if (ch == '0') score[j]++;
                else {
                    num[i]++;
                    check[i][j] = true;
                }
            }
        }
        //지학이의 최종 점수
        int ans_score = 0;
         
        memset(p_score, 0sizeof(p_score));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= T; j++) {
                if (check[i][j] == true) {
                    p_score[i] += score[j];
                }
            }
        }
        ans_score = p_score[P];
        //지학이의 등수
        int ans_rank = 1;
        for (int i = 1; i <= N; i++) {
            if (i == P) continue;
            if (ans_score < p_score[i]) ans_rank++;
            else if (ans_score == p_score[i] && num[P] < num[i]) ans_rank++;
            else if (ans_score == p_score[i] && num[P] == num[i] && P > i) ans_rank++;
        }
        printf("%d %d\n", ans_score, ans_rank);
    }
    return 0;
}
cs

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'swea 문제풀이' 카테고리의 다른 글

swea 8888 시험  (2) 2020.01.27