글 읽기 - 시간초과인데 시간복잡도를 어떻게 더 줄일지 모르겠습니다.

pwc99 5년 전 0

코드와 같이 우선 순열을 모두 save배열에 저장한 후,

O(n²)으로 중복체크하였습니다.

8 8

1 2 3 4 5 6 7 8

예제를 시행하면
^{40000회*40000회로 시간초과가 나는 것 까지는 알겠으나,}

^{중복체크를 어떻게 해야하는지 모르겠습니다.}

#include <iostream>
#include <algorithm>

using namespace std;

int N,M;
int input[10];
int arr[10];
bool visit[10] = {false};
int save[10][50005];
int save_i=0;
bool same_check[50005] = {false};

void func(int cnt){
    if(cnt > M) {
        for(int i=1;i<=M;i++)
            save[i][save_i] = arr[i];
        save_i++;
        return;
    }
    for(int i=1;i<=N;i++) {
        if(visit[i])
            continue;
        arr[cnt] = input[i];
        visit[i] = true;
        func(cnt+1);
        visit[i] = false;
    }
}

int main(void) {
    cin >> N >> M;
    for(int i=1;i<=N;i++)
        cin >> input[i];
    sort(input+1,input+N+1);
    func(1);
    //중복 수열 same_check배열에 체크.
    for(int i=0;i<save_i;i++) {
        for(int j=i+1;j<save_i;j++) {
            for(int k=1;k<=M;k++) {
                if(save[k][i] != save[k][j])    //중복 아닌 경우
                    break;
                if(k==M)    //중복 수열인 경우
                    same_check[j] = true;
            }
        }
    }

    //중복 아닌 수열만 출력
    for(int i=0;i<save_i;i++) {
        if(same_check[i])
            continue;
        for(int j=1;j<=M;j++)
            cout << save[j][i] << ' ';
        cout << '\n';
    }
    return 0;
}

pwc99 5년 전 0

https://www.acmicpc.net/problem/15664

N과M (10)은 제약조건이 추가되어 오히려 시간초과가 안뜹니다..

bakpark 5년 전 2

크기 순서가 주어진 길이 N짜리 배열에서

만약 정렬된 상태라면 O(N) 만에 중복제거를 할 수 있습니다.

지금 현재 풀이에서는 정렬을 하는게 우선이겠네요

bakpark 5년 전 1

다시보니 정렬이 된 상태로 저장이되네요

중복제거 힌트를 조금 드리면

1 1 2 2 3 3 3

이라는 수열이 있을때

int prev=0;

for(int i=1;i<=N;i++){
if(prev<arr[i]) {

prev = arr[i];

continue;

}

else same_chek[i] = true;

}

의 방식으로 할 수 있습니다.

Green55 5년 전 1

크기가 10000인 배열을 잡아서 수들이 몇번이나 등장하는지 세두시면 백트래킹으로 쉽게 해결하실 수 있습니다

pwc99 5년 전 0

처음에 중복 제거하고, 나온 수 체크해 백트래킹하니 잘 나옵니다!

답변 감사합니다~~

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

문제

문제

출처

ICPC

시간초과인데 시간복잡도를 어떻게 더 줄일지 모르겠습니다.

pwc99 5년 전 0

pwc99 5년 전 0

bakpark 5년 전 2

bakpark 5년 전 1

Green55 5년 전 1

pwc99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말