글 읽기 - 발전소 너무 어렵네요 ㅠ

gkfkagkfka12 5년 전 0

질문란에 있는 케이스를 다 해봤는데도 맞는데 어떤게 문제인지 모르겠습니다.

초기 상태가 p를 만족시키는 경우도 포함했습니다.

뭐가 문제일까요 ㅠㅠ

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1000000000;
int cost[17][17], dp[1 << 17], n, p, start;
string factory_state;

int fix(int state)
{
	// 최소로 켜야 하는 p개이상으로 켜져있는 경우면 0 리턴
	if (state >= ((1 << p) - 1)) return 0;
	// 위 조건을 만족못하고 전부 꺼져있는 상황이라면 -1 리턴
	if (state == 0) return -1;

	int &ret = dp[state];
	if (ret != -1)return ret;

	ret = INF;
	for (int i = 0; i < n; i++) {
		// 켜져 있는 발전소 찾는다.
		if (state&(1 << i)) {
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				// 꺼져있는 발전소 찾는다.
				if ((state&(1 << j)) == 0)
					// 꺼져있는 걸 켠 상태를 넘기고 모두 켜질 때까지 계산
					ret = min(ret, fix(state | (1 << j)) + cost[i][j]);
			}
		}
	}
	return ret;
}

int main(void)
{
	memset(dp, -1, sizeof(dp));
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> cost[i][j];
	}
	cin >> factory_state >> p;

	for (int i = 0; i < factory_state.size(); i++) {
		if(factory_state[i]=='Y')
			start |= (1 << i);
	}

	printf("%d", fix(start));
		
	return 0;
}

portableangel 5년 전 2

3
0 100 100
100 0 100
100 100 0
NNY
2

답은 누가 봐도 100입니다.

그러나 코드는 0을 출력합니다.

그 이유는 14번 줄 때문인데요, 비트 수와 수의 크기는 아무런 관계가 없습니다.

이진수 011보다 이진수 100이 크기 때문에 현재 코드는 처음에 발전소가 하나만 켜져있음에도 불구하고 그냥 "번호가 큰" 발전소가 켜져있다는 이유로 발전소가 많이 켜져있다고 판단하고 있습니다.

gkfkagkfka12 5년 전 0

@portableangel 감사합니다! 해결했습니다!

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

문제

문제

출처

ICPC

발전소 너무 어렵네요 ㅠ

gkfkagkfka12 5년 전 0

portableangel 5년 전 2

gkfkagkfka12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말