글 읽기 - 1107 리모컨 진짜 어디서 문제인지 모르겠습니다...

dreammusic23 8년 전 0

큐에 넣어서 숫자를 쌓는 방식으로 완전탐색하게 했습니다!

랜덤으로 돌려서 테스트도 해봤는데 크리티컬 케이스를 못 찾는건지 다 맞았다고 뜨는데 ㅠㅠ

대체 어디서 뭐가 문제인지...

#include <stdio.h>
#define INF 987654321
#define min(a,b) (a<b?a:b)
#define abs(a) ((a)<0?-(a):a)
int con[10];
int check[2][1000001];
int queue[1000001],front,rear;
int bfs(int n){
	int x,i,M=INF,N=0,temp=INF;
	for(i=0;i<10;i++){
		if(con[i]==-1||abs(n-i)>M) continue;
		queue[rear++]=i;
		check[0][i]=1;
		check[1][i]=abs(n-i);
		if(M>=check[1][i]){
			M=check[1][i];
			N=check[0][i];
		}
	}
	while(front<rear){
		x=queue[front++];
		for(i=0;i<10;i++){
			if(con[i]==-1) continue;
			int xx=x*10+i;
			if(abs(n-xx)>M||xx<10||check[0][xx]) continue;
			queue[rear++]=xx;
			check[0][xx]=check[0][x]+1;
			check[1][xx]=abs(n-xx);
			if(M>=check[1][xx]){
				M=check[1][xx];
				N=check[0][xx];
			}
			//printf("xx:%d M:%d N:%d x:%d check0:%d check1:%d\n",xx,M,N,x,check[0][x],check[0][xx]);
		}
	}
	return M+N;
}
int main(){
	int n,m,i,num,sum;
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d",&num);
		con[num]=-1;
	}
	sum=bfs(n);
	printf("%d\n",min(sum,abs(n-100)));
	return 0;
}

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

문제

문제

출처

ICPC

1107 리모컨 진짜 어디서 문제인지 모르겠습니다...

dreammusic23 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말