글 읽기 - 2098번 외판원 문제 INT

chhi0123 6년 전 0

와 1시간 동안 헤매다가 틀린 원인을 찾긴 했는데, 왜 이게 문제가 되는지 모르겠네요..

도무지 모르겠어서 질문 올립니다.

대충 푸는 법은 탑다운 식으로다가 현재 방문지점들을 비트로 표시하고 방문안한 지점들을 들리는 다이나믹 프로그래밍인데요,

22번째 줄부터 현재지점 p와 방문상태비트 stat을 갖고 나머지 지점들을 방문해볼까 계산하는 파트입니다.

문제에서 최소값을 원하니까 최소값을 저장할 변수 m은 인트의 최대값을 일단 가지게 했습니다.

포문 돌면서 m이 갱신이 되고 리턴하는 구존데,

m을 INT_MAX로 하면 틀리고, 대충 적당히 큰 값으로 하면 맞습니다.

이전까지 다이나믹 프로그래밍에서 최소값을 찾는 문제면 항상 INT_MAX를 써왔던터라 어안이 벙벙하네요.

INT_MAX와 min()을 같이 쓰면 에러나는 특수한 경우라도 있는 걸까요?

#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;

int n, all;
int cost[16][16];
int dp[16][1 << 16];

int func(int cur, int stat) {
	if (stat == all) {
		if (cost[cur][0] == 0)
			return 987654321;
		else
			return cost[cur][0];
	}

	int& ref = dp[cur][stat];
	if (ref != 0)
		return ref;

	int m = INT_MAX;
	for (int i = 1; i < n; ++i) {
		if (((stat&(1 << i)) == 0) && (cost[cur][i] != 0))
			m = min(m, func(i, (stat | (1 << i))) + cost[cur][i]);
	}

	return ref = m;
}

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

	printf("%d", func(0, 1));
	return 0;
}

3587jjh 6년 전 1

25번째줄에 func(i, (stat | (1 << i))) + cost[cur][i] 에서

func가 INT_MAX를 리턴하면 오버플로우가 나요

m = min((long long)m, (long long)func(i, (stat | (1 << i))) + cost[cur][i]

로 바꾸니까 맞네요

chhi0123 6년 전 0

감사합니다 min()질 햇는데도 여전히 INT_MAX인 경우를 생각못했네요 ㅜㅜ

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

문제

문제

출처

ICPC

2098번 외판원 문제 INT_MAX 관련 질문

chhi0123 6년 전 0

3587jjh 6년 전 1

chhi0123 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말