글 읽기 - 시간초과 ㅠ

gessetggi 5년 전 0

시간초과가 자꾸뜨는데 어디에서 시간을 많이 잡아먹는지 모르겠어요 ㅠㅠ

친구는 depth == M에서 집의 위치와 치킨집 위치를 알아내는것으로 4중 for문을 돌렸는데도 시간초과가 안나는데 이 코드는 어디에서 수정이 필요할까요...?

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

int num[52][52];
int a_local[102][2];
int b_local[15][2];
int c_local[15][2];
int h_count = 0;
int c_count = 0;
int N, M, T;
int result;
int check[15];

void back(int a, int depth)
{
	if (depth == M) //M개가 되면 최소구하기 시작
	{
		int temp = 0;

		for (int i = 0; i < h_count; i++)
		{
			
			int sum = abs(a_local[i][0] - c_local[0][0]) + abs(a_local[i][1] - c_local[0][1]);
			for (int j = 1; j < M; j++)
			{
				if (sum > (abs(a_local[i][0] - c_local[j][0]) + abs(a_local[i][1] - c_local[j][1])))
					sum = abs(a_local[i][0] - c_local[j][0]) + abs(a_local[i][1] - c_local[j][1]);
			}
			temp = temp + sum;
		}
		
		if (result == 0)
			result = temp;
		else if(temp < result)
			result = temp;
	}
	else
	{
		for (int i = a; i < c_count; i++) //치킨집 M개 채우기
		{
			if (check[i] == 1)
				continue;
			check[i] = 1;
			c_local[depth][0] = b_local[i][0];
			c_local[depth][1] = b_local[i][1];
			back(a+1, depth + 1);
			check[i] = 0;
		}
	}
}

int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			scanf("%d", &num[i][j]);
			if (num[i][j] == 1) //집의 위치 저장
			{
				a_local[h_count][0] = i;
				a_local[h_count][1] = j;
				h_count++;
			}
			else if (num[i][j] == 2) //치킨집의 위치 저장
			{
				b_local[c_count][0] = i;
				b_local[c_count][1] = j;
				c_count++;
			}
		}
	}

	back(0, 0);
	printf("%d\n", result);
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 ㅠ

gessetggi 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말