글 읽기 - 1780번 데이터 타입이 시간에 영향을 끼칠까요?

여러가지 방법으로 코드를 작성했는데 계속 시간초과가 발생합니다.

그러던 중 70번 줄에 처음 2차원 벡터를 선언했던 부분을

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int neg, zero, pos;
int** mat;
vector<int> recursive(int n, int startX, int startY) {
    vector<int> result(3, 0);
 
    int tmpNeg, tmpZero, tmpPos;
    tmpNeg = 0;
    tmpZero = 0;
    tmpPos = 0;
    vector<int> tmp;
    bool flag = true;
 
    int sameVal = mat[startX][startY];
    for (int p = startX; p < startX + n; p++) {
        for (int q = startY; q < startY + n; q++) {
            if (sameVal != mat[p][q]) {
                flag = false;
                break;
            }
        }
    }
 
    if (flag) {
        if (sameVal == -1) {
            tmpNeg++;
        } else if (sameVal == 0) {
            tmpZero++;
        } else {
            tmpPos++;
        }
    } else {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                tmp = recursive(n / 3, startX + i * n / 3, startY + j * n / 3);
                tmpNeg += tmp[0];
                tmpZero += tmp[1];
                tmpPos += tmp[2];
            }
        }
    }
 
    result[0] = tmpNeg;
    result[1] = tmpZero;
    result[2] = tmpPos;
 
    return result;
}
int main(void) {
    int n;
 
    scanf("%d", &n);
 
    mat = new int*[n];
    for (int i = 0; i < n; i++) {
        mat[i] = new int[n];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &mat[i][j]);
        }
    }
    neg = zero = pos = 0;
 
    vector<int> answer = recursive(n, 0, 0);
    printf("%d\n%d\n%d", answer[0], answer[1], answer[2]);
    return 0;
}
Colored by Color Scripter
cs

위 코드처럼 int 배열로 변경하였습니다.

그랬더니 바로 정답으로 처리가 되더군요..

알고리즘 자체가 문제인 것으로 여겨 시간복잡도를 줄여보고자 엄청 많은 시도들을 했는데,

매개변수로 계속 전달해주던 vector mat을 없애고

전역벽수로 2차원 배열을 할당해주니 해결이 되는..

vector를 생성하고 매개변수로 계속 재귀 함수에 넘겨주는 것 만으로 시간에 많은 영향을 끼치나요?

문제

문제

출처

ICPC

1780번 데이터 타입이 시간에 영향을 끼칠까요?

psj1028 3년 전 0

bupjae 3년 전 2

slah007 3년 전 2

psj1028 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말