글 읽기 - 1102번 문제 시간초과 질문입니다.

ksw51101 2년 전 0

비트마스크와 DP와 DFS를 사용하였습니다.

현재 상태에서 꺼져있는 발전소를 고르고 이미 켜져있는 발전소에서 꺼져있는 발전소를 켜는데 필요한 최소값을 구하여 현재 cost에 더했습니다.

cost가 이미 구한 최소값보다 커지면 재귀를 더 이상 하지 않도록 하였고 p의 값보다 크거나 같아지면 정답인 ans를 최소값으로 변경하였습니다.

다른 분들이 작성한 코드와 큰 차이는 없는 것 같은데 시간초과가 발생하여 조언 부탁드립니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321

int n, p, ans = INF;
int d[1 << 16];
vector<vector<int>> vec;

int minCost(int state, int num) { //state에서 num번째 발전소를 켜는데 드는 최소비용
	int cost = 51;

	for (int i = 0; i < n; i++) {
		if ((1 << i) & state) {
			cost = min(cost, vec[i][num]);
		}
	}
	return cost;
}

int bit_Count(int num) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if ((1 << i) & num)
			cnt++;
	}
	return cnt;
}

void DFS(int state) {
	if (d[state] > ans) return; //정답보다 cost가 커지면 더 이상 볼 필요가 없다.

	if (bit_Count(state) >= p) { //켜져 있어야 하는 발전소의 개수 이상이 되면 ans 갱신
		ans = min(ans, d[state]);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!((1 << i) & state)) { //꺼져있는 발전소를 찾으면
			int new_state = state | (1 << i); //그 발전소를 켜고
			d[new_state] = min(d[new_state], d[state] + minCost(state, i)); //새로운 상태에서의 cost를 최소값으로 변경
			DFS(new_state);
		}
	}
}

int main() {
	cin >> n;
	fill(&d[0], &d[1 << 16], INF);

	for (int i = 0; i < n; i++) {
		vector<int> temp(n);
		for (int j = 0; j < n; j++) {
			cin >> temp[j];
		}
		vec.push_back(temp);
	}
	int state = 0, cnt = 0;
	for (int i = 0; i < n; i++) {
		char temp;
		cin >> temp;
		if (temp == 'Y') {
			state = state | (1 << i);
			cnt++;
		}
	}
	d[state] = 0;
	cin >> p;

	if (!cnt && p != 0)
		ans = -1;
	else 
		DFS(state);

	cout << ans << '\n';

	return 0;
}

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

문제

문제

출처

ICPC

1102번 문제 시간초과 질문입니다.

ksw51101 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말