글 읽기 - 왜 틀렸는지 모르겠습니다 ..ㅠㅠ

kdhsong 7년 전 1

어디가 틀렸는지 좀 봐주세요 ..ㅠㅠㅠㅠㅠㅠㅠ

그리고 어떤발전소만 체크했는지만 봐도 갯수의 정보가

있기때문에 1차원배열로 캐시만으로도 될 것 같은데 제 생각이 맞을까요?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define INF		987654321

using namespace std;

int cache[130000][18];
int n,p;
int cost[18][18];
char str[18];

int back(int bit, int cnt){

	if(cnt == p)	return 0;

	int &ret = cache[bit][cnt];
	if(ret != -1)		return ret;

	ret = INF;

	for(int i = 0; i < n; i++){
	
		if( !((1<<i)&bit) ) // 이 발전소는 아직 안켜짐
		{
			for(int j = 0; j < n; j++)
			{
				if(i == j)	continue;

				if( ((1<<j) & ((1<<i)|bit)) ) // j번째 발전소가 켜져있다면
				{
					ret = min(ret,back( (1<<i)|bit , cnt+1) + cost[j][i]); 
				}
			}
		}
	}

	return ret;
}

int main(){
	
	memset(cache,-1,sizeof(cache));

	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			scanf("%d",&cost[i][j]);

	scanf("%s %d",str,&p);

	int state = 0;
	int num = 0;

	for(int i = 0; str[i] != '\0'; i++){
		if(str[i] == 'Y'){
			num++;
			state = (state | (1 << i));
		}
	}
	int ret = 0;

	ret = back(state,num);
	

	printf("%d",ret);
	
}

etaehyun4 7년 전 1

네 bit가 결정되면 cnt가 알아서 결정되므로 1차원도 가능합니다.

p개가 켜져있는 것이 아니라 "적어도" p개가 켜져있는 것이 목표인 것을 확인해보세요

kdhsong 7년 전 0

궁금한점 모두 해결해주셔서 감사합니다!! ㅎㅎ

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다 ..ㅠㅠ

kdhsong 7년 전 1

etaehyun4 7년 전 1

kdhsong 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말