글 읽기 - 15686 치킨배달 질문이요 고수님들 ㅠㅠ 도와주세요

jgb5131 5년 전 0

안녕하세요 제가 치킨배달 문제를 3번정도 풀고있는데

오늘은 안풀려서 계속 틀렸습니다가 나오더라고요 그런데 아무리 생각해도 틀린부분이 없어서 코드를 하나씩 살펴봤는데

초기화를 할때 1번경우에서는 틀렸습니다. 가 나오고

2번경우에선 맞았습니다 가 나옵니다.

1번과 2번의 차이는 bool check 배열과 int d 배열의 순서만 바꾸고 나머지는 그대로입니다.

순서가 변경되면서 배열의 크기가 변한것도 아니고 그냥 순서만 바꿧는데

하나는 틀렸습니다. 하나는 맞았습니다가 나오네요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

고수님들 제발 도와주세요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

// 1번경우
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 98765432;
int map[51][51];
bool check[15];
int d[51][15];
vector<pair<int, int>> people;
vector<pair<int, int>> chicken;
// 2번경우
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 98765432;
int map[51][51];
int d[51][15];
bool check[15];
vector<pair<int, int>> people;
vector<pair<int, int>> chicken;

Green55 5년 전 1

코드에서 배열의 범위를 벗어난 곳에 접근하는 등의 오류가 있으면 똑같은 코드를 제출해도 맞을 수도 있고, 틀릴 수도 있습니다.

코드 전체를 올려주시는게 아니면 이것만으로는 알 수 없습니다.

jgb5131 5년 전 0

전체코드입니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 98765432;
int map[51][51];
bool check[15];
int d[51][15];
vector<pair<int, int>> people;
vector<pair<int, int>> chicken;
int N, M, res;
int get_result() {
	int ans = 0;
	for (int i = 0; i < people.size(); i++) {
		int min_dist = MAX;
		for (int j = 0; j < chicken.size(); j++) {
			if (check[j]) min_dist = min(min_dist, d[i][j]);
		}
		ans += min_dist;
	}
	return ans;
}
void dfs(int idx, int cnt) {
	check[idx] = true;
	if (cnt == M) {
		res = min(res, get_result());
	}
	else {
		for (int i = idx + 1; i < chicken.size(); i++) {
			if (!check[i]) {
				check[i] = true;
				dfs(i, cnt + 1);
				check[i] = false;
			}
		}
	}
	check[idx] = false;
}
int main() {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) { // 집
				people.push_back(make_pair(i, j));
			}
			if (map[i][j] == 2) { // 치킨집
				chicken.push_back(make_pair(i, j));
			}
		}
	}
	// 미리 거리 정해놓음
	for (int i = 0; i < people.size(); i++) {
		for (int j = 0; j < chicken.size(); j++) {
			d[i][j] = abs(people[i].first - chicken[j].first) + abs(people[i].second - chicken[j].second);
		}
	}
	res = MAX;
	for (int i = 0; i < chicken.size(); i++) {
		dfs(i, 1);
	}
	printf("%d \n", res);
	return 0;
}

Green55 5년 전 1

집이 최고 99개까지 있을 수 있는데(집의 개수는 2N개를 넘지 않으며), d[51][]로 선언이 되있습니다.

jgb5131 5년 전 0

아.. ㅠㅠ 문제를 제대로 읽어야겠네요

정말 감사합니다~

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

문제

문제

출처

ICPC

15686 치킨배달 질문이요 고수님들 ㅠㅠ 도와주세요

jgb5131 5년 전 0

Green55 5년 전 1

jgb5131 5년 전 0

Green55 5년 전 1

jgb5131 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말