글 읽기 - 발전소 문제 질문드립니다

kskung2 7년 전 0

비트마스크로 상태공간 만들어서 해결하려고 했는데 어느 부분에서 틀렸는지 감이 잘 오지않습니다.ㅠㅠ

구현방식이 잘못되었나요?

#include <stdio.h>
#define MAX 1<<16
#define INF 987654321
int cost[17][17];
int arr[17][MAX]; // i,j   j상태에서 i를 키려고 할 때
int n, p;
char state[17];
int min(int a, int b)
{
	return a < b ? a : b;
}
int f(int index, int cnt,int cur)
{
	if ((cur == (1 << n) - 1) || cnt >= p)
	{
		if (cnt == p)
			return 0;
		else
			return INF;
	}

	int r = arr[index][cur];

	if (r != -1)
		return r;

	r = INF;
	for (int i = 1; i <= n; i++)
	{
		if (!(cur & (1 << (i - 1))))//방문 ㄴ
		{
			if (state[i - 1] == 'Y') // 켜져 있을 때
			{
				r = min(r, f(i, cnt + 1, cur + (1 << (i-1)) ) );
			}
			else if(index) // i 를 키려고 할 때
			{
				int ct = INF;
				for (int j = 1; j <= n; j++) {
					if ((cur & (1 << (j - 1))) && cost[j][i])
						ct = min(ct, cost[j][i]);
				}
				r = min(r, f(i, cnt + 1, cur + (1 << (i - 1))) + ct);
			}
		}
	}
	arr[index][cur] = r;
	return r;
}
int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			scanf("%d", &cost[i][j]);
		}
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= 1 << n; j++) {
			arr[i][j] = -1;
		}
	}
	scanf("%s", state);
	scanf("%d", &p);
	int ret = f(0, 0, 0);
	printf("%d", ret!=INF ? ret :-1);
	return 0;
}

orange4glace 7년 전 1

dp 구현을 잘못하신것같습니다.

현재는 dp[현재 키는 인덱스][상태] ? 이렇게 하신것 같은데

dp[상태] 를 이용해서 1차원dp 해결할 수 있습니다.

상태 하나만으로 어떤 발전소들이 켜져있는지 알 수 있고, 켜져있는 발전소의 숫자도 알 수 있기 때문이죠

그리고 if (state[i - 1] == 'Y') // 켜져 있을 때

로 처리를 하고계신데, 이건 최초 발전소의 상태에 대한 정보만 가지고있기 때문에 해당 조건문을 가지고는 현재 상태에서 발전소가 켜져있는지 아닌지 판단할 수 없습니다.

if (cur & (1 << (i - 1)) 로 하셔야 겠지요.

kskung2 7년 전 0

저기 켜져 있을 때 처리한 부분도 최초상태에서 켜야하는 발전소들에 대해서만 가중치를 더한다는 생각으로 켜야하는 발전소들만

해당 상태의 켜져있는 발전소들 중에서 가중치를 더하는식으로 구현을 했는데 켠 순서가 상관이 없으니 1차원으로 해결이 가능하겠네요.

1차원으로 수정하고도 아직 정답이...

그럼 아래 소스처럼 어떤 상태에 대해 꺼져있는 발전소를 켤 수 있는 경우를 생각해서 최소값을 갱신해나가는 식으로 구현을 했는데

처리가 조금 미흡한지 정답이 아니네요ㅠ 이런유형 처음풀어보는거라 아직 익숙치가 않아서..

혹시 이 방법도 잘못된 부분이 있나요

#include <stdio.h>
#define MAX 1<<17
#define INF 987654321
int cost[17][17];
int arr[MAX]; // i,j   j상태에서 i를 키려고 할 때
int n, p;
char state[17];
int min(int a, int b)
{
	return a < b ? a : b;
}
int main()
{
	int i, j,result = INF;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			scanf("%d", &cost[i][j]);
		}
	}
	scanf("%s", state);
	scanf("%d", &p);
	for (j = 0; j < MAX; j++) {
		arr[j] = INF;
	}
	int cur = 0,cnt = 0;
	for (i = 0; i < n; i++)
	{
		if (state[i] == 'Y') {
			cur += 1 << i;
			cnt++;
		}
	}
	if (cnt >= p)
	{
		printf("0");
		return 0;
	}
	arr[cur] = 0;
	int index = 1 << n;
	for (i = cur; i < index; i++)
	{
		int ct = INF,count = 0;
		for (j = 1; j <= n; j++)
		{
			if (i & (1 << (j - 1))) // 켜져있는 발전소에 대하여
			{
				count++;
				for (int k = 1; k <= n; k++)
				{
					if (cost[j][k] && !(i & 1 << (k - 1))) // j 가 k 를 켤 수 있다
					{
						arr[i + (1 << (k - 1))] = min(arr[i + (1 << (k - 1))], arr[i] + cost[j][k]);
					}//i 상태에서 j로 k를 켬
				}
			}
		}
		if (count >= p) //p개 이상 켜져있을 때
			result = min(result, arr[i]);
	}
	printf("%d", result != INF ? result : -1);
	return 0;
}

orange4glace 7년 전 1

문제가 다른곳에 있었네요 ^^;

발전소를 가동하는데 필요한 비용이 0인 경우도 있네요.

if (cost[j][k] 조건을 없애주시면 정답이 나옵니다.

가장 처음 올려주신 소스코드도 해당 조건을 제거하면 정답이 나오네요!

그리고 두번째 소스에서

if (cost[j][k] && !(i & 1 << (k - 1))) // j 가 k 를 켤 수 있다

에 & 연산 뒤에 괄호가 하나 빠져있어요

그것도 고쳐주시면 정답으로 나오네요 !!

kskung2 7년 전 1

비트연산할 때 괄호가 상당히 중요하네요 .. ㅎㅎ

첫번 째 말씀하신 것도 문제 조건에 비용이 자연수라고 되어있어서 0을 포함시키지 않았는데 . . 이상하군요 ㅋㅋㅋ

미흡한점 많이봐주셔서 감사합니다 ~~ 덕분에 잘 해결되었어요!

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

문제

문제

출처

ICPC

발전소 문제 질문드립니다

kskung2 7년 전 0

orange4glace 7년 전 1

kskung2 7년 전 0

orange4glace 7년 전 1

kskung2 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말