글 읽기 - C++ 배열과 벡터 차이? 배열로 되는데, 벡터로는 초과시간.. 질문드려요 ㅠ

djswpsk1024 6년 전 0

삼성 SW Expert Academy 사이트에서 문제를 푸는데, 원인을 몰라서 질문드립니다. 전에도 이런 문제가 있어서서 차이가 무엇인지 너무 궁금합니다.

테스트케이스 50개 중에서 아래 코드로 실행하면 다 실행되는데,

만약에 6,7번째 줄을 주석처리하고

8,9번째 줄을 주석 풀고 실행하면 43번째 테스트케이스에서 시간초과가 뜹니다. 원인이 무엇일까요...? 초기화 사이즈도 안큰 것 같은데..

제가 벡터에 대해 잘 몰라서... 아무리 생각해도 시간초과가 뜰 이유가 없는데 차이점 설명해주실 수 있나요 ㅠㅠㅠㅠ

#include <iostream>
#include <vector>
#define INF 2e9
using namespace std;

int S[21][21];
bool visited[21];
//vector<bool> visited(21, false);
//vector<vector<int>> S(21, vector<int>(21, 0));
int ret;

//맛의 차이를 계산하기 위한 함수
int abs(int n){
    return n > 0 ? n : -n;
}

// 인자는 식재료 총 개수 N
// 현재까지 체크한 식재료 총 개수 cnt
// A음식에 사용할 남은 식재료 개수 food
void calcSynergy(int N, int cnt, int food){

    if(cnt == N){
        int A = 0, B = 0;

        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= N; ++j){
                if(i == j) continue;

                // A음식에 사용한 식재료는 visited 변수에 true로 저장되어 있음
                // 따라서 visited[i] && visited[j] 이면,
                // 둘 다 A 음식에 사용된 것이므로 A 변수에 저장
                if(visited[i] && visited[j]) A += S[i][j];

                if(!visited[i] && !visited[j]) B += S[i][j];
                // B음식에 사용될 식재료는 visited 변수에 false로 저장되어 있음
                // 따라서 !visited[i] && !visited[j] 이면,
                // 둘 다 B 음식에 사용된 것이므로 B 변수에 저장
            }
        }

        ret = min(ret, abs(A - B));
        return;
    }

    // food는 A음식에 사용해야할 식재료 갯수
    // 따라서, food가 0 이상이면, 현재 cnt번 식재료를 A에 사용한다고 체크함
    if(food > 0){

        // visited[] 변수에 표시한 뒤, 식재료 하나를 A 음식에 사용했으므로
        // cnt + 1, food - 1를 인자로 넘겨 재귀 호출
        visited[cnt] = true;
        calcSynergy(N, cnt + 1, food - 1);
        visited[cnt] = false;
    }

    // A음식에 사용하지 않는다면, B음식에 사용할 식재료 하나를 음식에 저장했으므로
    // cnt + 1, food를 인자로 넘겨 재귀 함수 호출
    calcSynergy(N, cnt + 1, food);
}

int main() {
    int T, N, problemNum = 1;
    cin >> T;

    while(T--){
        cin >> N;

        //S = vector<vector<int>>(N+1, vector<int>(N+1, 0)); // S를 가로, 세로 N 크기의 2차원 배열로 생성

        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= N; ++j){
                cin >> S[i][j];
            }
        }

        ret = INF;

        calcSynergy(N, 0, N/2);
        cout << "#" << problemNum << " " << ret << endl;
        problemNum++;
        //S.clear();
    }

    return 0;
}

startlink 6년 전 1

SWEA 사이트에서 컴파일 옵션을 어떻게 주는지 모르겠지만, Optimization flag가 없으면 STL이 좀 느립니다.

djswpsk1024 6년 전 0

그럼 우선 코드 상에 문제는 없어보이고, Optimization flag로 인한 성능 차이인건가요...???

만약 그렇다면.. 사이트에서 제가 처리할 방법은 없는거죠?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 배열과 벡터 차이? 배열로 되는데, 벡터로는 초과시간.. 질문드려요 ㅠ

djswpsk1024 6년 전 0

startlink 6년 전 1

djswpsk1024 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말