글 읽기 - 시간초과 나는데요..<전체코드있어요><리뷰 부탁드려요..ㅠ>

jennifer92 6년 전 0

벡터를 사용한게 원인일까요...?

틀렸으니 다 올려도 괜찮을것같아서 전 그냥 올립니다.

입력받을때, 특정위치를 벡터로 받았는데요....

이게 시간초과의 원인인가요??ㅠㅠㅠ...

#include<iostream>
#include<vector>
using namespace std;

int city[50][50] = { 0 };
int selectstore[13] = { 0 };

struct pos {
	int x; int y;
};

vector<pos> client;
vector<pos> store;
int presentsum = 9999;
// N개 중 M개를 골라야함.n번째껄 선택하느냐 마느냐

int SUM(){
	int tempsum = 0;
	for (int j = 0; j < client.size(); j++)
	{
		int tempmin = 9999;
		for (int i = 0; i < store.size(); i++)
		{
			if (selectstore[i] == 1)
			{
				int distance = abs(client[j].x - store[i].x) + abs(client[j].y - store[i].y);
				if (distance < tempmin) tempmin = distance;
			}
		}
		tempsum += tempmin;
	}
	return tempsum;
}

int totalsum = 9999;
int delivery(int N, int M, int index, int cnt){
	int sum = 0;
	//스톱조건
	if (cnt > M || index > N)
		return 0;

	//가능조건
	if (cnt == M)
{
		/*for (int i = 0; i < N; i++)
		cout << selectstore[i];
		cout << endl;*/

		int tempsum = SUM();// 합구하기.
		if (tempsum < totalsum)
			totalsum = tempsum;
	
		return totalsum;
	}
	//지속조건
	selectstore[index] = 1;
	delivery(N, M, index + 1, cnt + 1);//선택할경우
	selectstore[index] = 0;
	delivery(N, M, index + 1, cnt);

	return sum;
}

int main(){

	int N, M;

	cin >> N >> M;

	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			cin >> city[j][i];
			if (city[j][i] == 1)
			{
				pos temp;
				temp.x = i; temp.y = j;
				client.push_back(temp);
			}
			if (city[j][i] == 2)
			{
				pos temp;
				temp.x = i; temp.y = j;
				store.push_back(temp);
			}
		}
	}

	//입력 끝
	int index = 0; int cnt = 0;
	delivery(N, M, index, cnt);
	cout << totalsum; // N,개중 M개를 골라야함.n번째껄 선택하느냐 마느냐

	return 0;
}

jseo 6년 전 1

if (cnt > M || index > N) 조건문에서 index > N 이 아니라 index > store.size() 가 되어야 합니다.

그리고 cnt > M 을 따로 체크할 필요는 없습니다.

jseo 6년 전 1

index >= store.size() *

jennifer92 5년 전 0

아! 그렇군요! 정말 감사합니다 !! ㅠㅠ!

덕분에 원인을 찾았어요!

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

문제

문제

출처

ICPC

시간초과 나는데요..<전체코드있어요><리뷰 부탁드려요..ㅠ>

jennifer92 6년 전 0

jseo 6년 전 1

jseo 6년 전 1

jennifer92 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말