글 읽기 - 3653번 시간초과 질문드립니다ㅜ

jane0013 9년 전 0

채점하면서 계속 시간초과가 뜨는데

다른 아이디어로 다시 짜야할까요..?

도무지 방법이 생각이 안나네요ㅠㅠ

#include<stdio.h>
#include<stdlib.h>

void check(int a,int b,int* arr);

int main(){
	int num;
	int i,j;
	int* a;
	int* b;
	int** arr;

	scanf("%d",&num);

	arr=(int**)malloc(sizeof(int*)*num);

	a=(int*)malloc(sizeof(int)*num);
	b=(int*)malloc(sizeof(int)*num);

	for(i=0;i<num;i++){
		scanf("%d %d",a+i,b+i);

		*(arr+i)=(int*)malloc(sizeof(int)*b[i]);

		for(j=0;j<b[i];j++)
			scanf("%d",*(arr+i)+j);

		getchar();
	}

	for(i=0;i<num;i++){
		check(a[i],b[i],*(arr+i));
	}

}


void check(int a,int b,int* arr){
	int* build=(int*)malloc(sizeof(int)*a);
	int i,j,k;
	int save;
	int tempsave;

	for(i=0;i<a;i++)
		build[i]=i+1;
	
	for(i=0;i<b;i++){
		for(j=0;j<a;j++){
			if(arr[i]==build[j])
				save=j;
		}

		tempsave=build[save];

		for(k=save-1;k>=0;k--)
			build[k+1]=build[k];
		
		build[0]=tempsave;

		printf("%d ",save);

	}
	printf("\n");
}

Nada 9년 전 0

위 방법은 O(N^2) 솔루션인데

특정 값을 update하는 것과 일정 구간의 합을 O(logN) 만에 구하는 방법이 있습니다.

인덱스 트리나 펜윅트리를 이용해 구할 수 있는데 이 문제를 풀기 전에

https://www.acmicpc.net/problem/1275 이 문제를 풀고 도전하시는 게 나을 것 같아요.

이 방법을 이용해 O(NlogN)으로 문제를 풀 수 있습니다.

august14 9년 전 0

이 링크를 참고하세요

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

문제

문제

출처

ICPC

3653번 시간초과 질문드립니다ㅜ

jane0013 9년 전 0

Nada 9년 전 0

august14 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말