글 읽기 - 알고리즘이 맞는건지 모르겠즘.....

vegatrash 5년 전 0

예시 입출력은 다 제대로 나오긴하는데

제출하면 시간초과가 뜹니다.

보통 브루트 포스는 무조건 다 살펴보는거라 그대로 했는데 어디서 초과가 나는걸까요...

+ nCr함수에서 디버그 해보면 같은 조합이 중복되서 나오는 경우가 있는데 답에는 지장안주지만 이것때문에 시간초과가 나는건가요?...

근데 제가 이 함수랑 똑같은 구조로 중복없이 6603번 문제를 풀었거든요. 왜 여기서만 중복된게 또 나오는 경우가 생기는건가요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <time.h>
#include <memory.h>
#include <functional>

using namespace std;

typedef struct point {
	int x, y;
}Point;

int minimum = 2100000000, ch_n = 0;
int grid[51][51];
vector<Point> v; // chicken
vector<int> check(14);

int findleast(int x, int y) { // 현재 좌표에서 가장 가까운 치킨집과의 거리를 계산
	int min = 2100000000;
	for (int i = 0; i < v.size(); i++) {
		if (check[i] != 1) continue;
		int dist = abs(x - v[i].x) + abs(y - v[i].y);
		if (dist < min) min = dist;
	}
	return min;
}

void ncr(int n, int r, int count, int size) { // 치킨집 n개 중 r개를 선택하여 계산을 함
	if (count == r) {
		for (int i = 0; i < check.size(); i++) { // 몇 번째 치킨집이 선택된건지 디버그용으로 넣었음
			cout << check[i] << " ";
		}
		cout << endl;
		int temp_sum = 0;
		for (int i = 0; i < size; i++) { // 선택된 r개의 치킨집에 대해 거리를 계산함
			for (int j = 0; j < size; j++) {
				if (grid[i][j] == 1) {
					temp_sum += findleast(i, j);
				}
			}
		}
		if (temp_sum < minimum) minimum = temp_sum;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (check[i] == 1) continue;
		check[i] = 1;
		ncr(n, r, count + 1, size);
		check[i] = 0;
	}
	return;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) { // 입력부분. 입력이 2(치킨집) 이면 치킨집 리스트에 그 좌표를 push.
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 2) {
				Point temp = { i, j };
				v.push_back(temp);
				ch_n++;
			}
		}
	}
	ncr(ch_n, m, 0, n);
	cout << minimum;

	return 0;
}

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

문제

문제

출처

ICPC

알고리즘이 맞는건지 모르겠즘.....

vegatrash 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말