글 읽기 - 시간복잡도 질문

namgyu 3년 전 0

그냥 다이나믹으로 돌려보니까 8ms 나오면서 정답으로 처리 되었긴한데..

채점한곳보니까 0ms로 다들 푸셨길래 다른 해법을 찾던 도중

큐를 이용하면 좀 더 빠를꺼같아 다시 풀었더니 시간이 2배이상으로 걸리네요...

아무리 생각해도 큐를 이용했을때 시간이 덜 나오면 덜 나올꺼 같았는데

제가 잘못 생각하고 있는건가요??

#include<stdio.h>
#define SIZE 1000001

int D[SIZE], Q[SIZE];
void func(int, int, int);

int main(void) {
	int x, v, front = 0;
	scanf("%d", &x);
	for (v = 1; v < x; v = Q[front++]){
		func(v, v * 3, x);
		func(v, v * 2, x);
		func(v, v + 1, x);
		if (v * 3 == x || v * 2 == x || v + 1 == x)
			break;
	}
	printf("%d\n", D[x]);
	return 0;
}

void func(int n, int v, int x) {
	static int rear = 0;
	if (v <= x && D[v] == 0) {
		Q[++rear] = v;
		D[v] = D[n] + 1;
	}
}

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

문제

문제

출처

ACM-ICPC

시간복잡도 질문

namgyu 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말