아마 이 문제 때문에 찾아오신 분들은 시간 초과 때문에 화가 나서 검색해 들어오셨을 텐데
문제 풀이는 생략하고 시간을 줄이는 방법에 대해 설명하겠습니다.ㅠㅠ
- 우선, 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, 0, sizeof(score));
memset(num, 0, sizeof(num));
memset(check, false, sizeof(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, 0, sizeof(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
지적, 조언 언제든지 환영입니다~~