글 읽기 - min이 작동 안되는 이유??

jungby1 4년 전 0

ret을 처음에 987654321로 초기화를 시킨 후 21번째 줄에서 ret = min(ret, min_cost(visited, i, left-1)+w[now][i]); 를 사용하여 ret을 갱신시켜주는 방식으로 코드를 짯습

니다. 그런데 자꾸 코드를 돌려보면 답이 987654321로 뜹니다;; min합수가 작동안할리는 없고 min_cost(visited, i, left-1)+w[now][i] 가 987654321의 값을 뛰어넘어서

그렇다고 생각했습니다... 그래서 min_cost(visited, i, left-1)+w[now][i] 값을 도중에 출력시켜보니 정상적으로 나오는데 도데체 min 함수가 작동을 안하는건지 아니면 제

가 놓치고 있는 부분이 있는지 제 짧은 소견으로는 도저히 이해할 수가 없습니다/.. 도와주십시오...

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 987654321;

int w[17][17];
int dp[17][1<<16];
int last;

int min_cost(int visited, int now, int left){
	int &ret=dp[left][visited];
	if(ret!=-1) return ret;
	if(left==0) {
		return 0;	
	}
	ret=inf;
	for(int i=1; i<=16; i++){
		if(((visited &(1<<i))==0) && (w[now][i]!=0)){
			visited |= (1<<i);
			ret = min(ret, min_cost(visited, i, left-1)+w[now][i]);
			visited &= ~(1<<i);
		} 
	}
	return ret;
}
int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	memset(dp,-1,sizeof(dp));
	memset(w,0,sizeof(w));
	int n;
	cin>> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> w[i][j];
		}
	}
	int ret,k;
	int visited=0;
	visited |= (1<<1);
	ret = min_cost(visited,1,n);

	cout << ret<<endl; 
	return 0;
}

pichulia 4년 전 1

dp배열의 크기가 작아보입니다.

그리고 현재 visit로만 dp를 돌리고있는데 이것만으론 정답을 구할 수 없습니다.

당장 눈에 보이는건... 도시를 다 돌고 다시 1로 돌아와야 하는데 현재 코드는 그렇게 돌 수가 없군요.

즉 left==0에 도달하지 못하고 min_cost 값이 도중에 정상적으로 나올 수 없어보입니다.

jungby1 4년 전 0

비트마스크 자릿수를 헷갈렸었네요... visited |= (1<<i) 에서 i의 자릿수가 그대로 들어가는 게 아니라 1이 증가한 상태로 저장된다는 사실을 간과했던 것 같습니다..

예를 들어서 2를 visited에 저장하려면 visited |= (1<<1) 인데 위 코드에는 그대로 들어가서 틀렸던 것 같습니다 .

이 점이랑 몇몇 사소한 부분들을 고치니깐 정답처리됬습니다. 감사합니다!!!

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

문제

문제

출처

ICPC

min이 작동 안되는 이유??

jungby1 4년 전 0

pichulia 4년 전 1

jungby1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말