글 읽기 - INF값 때문에요,c#만 이런건지.. 아니면 제가 코드를 잘못짠건지..

powerlsj7 1년 전 1

최소값을 구할려고 해서 int.MaxValue 로 int 최대값을 넣었습니다.

static int INF = int.MaxValue - 1000;

이부분 틀려서 -1000하니까 질문게시판의 반례가 통과하네요.

하지만 채점하면 틀리고

INF를 INF=987654321;

이값으로 하니까 채점이 통과합니다.

디버깅으로 값을 확인하면 -int최대값으로 나오는데 c#만 이런건가요? c++에서는 이런경우 없어서요 ㅠㅠ

만약 c#만 그렇다면 정말 쓰레기 언어같아용 ㅠㅠ

using System;
using System.IO;
namespace ThisIsCShaps
{
    class Program
    {

        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static string[] str;
        static int[,] w;
        static int n, t;
        static int[,] dp;
        static int INF = int.MaxValue - 1000;//이부분 틀려서 -1000하니까 질문게시판의 반례가 통과하네요.
        //하지만 채점하면 틀리고 INF를 INF=987654321; 이값으로 하니까 채점이 통과합니다.
        static int dfs(int start, int idx, int visit)
        {
            if (visit.Equals((1 << n) - 1))
            {
                //도착
                if (w[idx,start].Equals(0))
                {
                    return INF;
                }
                return w[idx, start];
            }

            if (!dp[idx, visit].Equals(-1))
            {
                return dp[idx, visit];
            }
            dp[idx, visit] = INF;
            for (int i = 0; i < n; i++)
            {
                t = (1 << i) & visit;
                if (t != 0 || w[idx, i] == 0)
                {
                    continue;
                }
                dp[idx, visit] = Math.Min(dp[idx, visit], dfs(start, i, visit | (1 << i)) + w[idx, i]);
            }

            return dp[idx, visit];
        }
        static void Main(string[] args)
        {
            n = int.Parse(sr.ReadLine());
            w = new int[n, n];
            dp = new int[n, 1 << n];
            for (int i = 0; i < n; i++)
            {
                str = sr.ReadLine().Split();
                for (int j = 0; j < n; j++)
                {
                    w[i, j] = int.Parse(str[j]);
                }
            }

            ResetDP();
            sw.Write(dfs(0, 0, 1));
            sw.Close();
        }
        static void ResetDP()
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < 1 << n; j++)
                {
                    dp[i, j] = -1;
                }
            }
        }
    }

}

kokosoko59 1년 전 1

40번째 줄 dfs(start, i, visit | (1 << i)) + w[idx, i] 에서 INF에 양수값을 더하는 경우가 생기는것같아요.

INF가 int max이면 양수값을 더할때 overflow 해서 음수가 되는거 아닐까요

powerlsj7 1년 전 0

아항 이해가 가네용 오홍

powerlsj7 1년 전 0

덕분에 소스코드 바꿨습니다. c++로도 풀고있어서 바꿨는데 바로 통과네용. 감사합니다. ㅎㅎ 재귀로 return받는 건 아직도 어렵네용.

#include<iostream>
#include<cstring>
using namespace std;
int n;
int dp[16][1 << 16];
int INF= 2147483647;
int w[16][16];
int dfs(int s, int idx, int visit)
{
	if (visit == (1 << n) - 1)
	{
		if (w[idx][s] == 0)
		{
			return INF;
		}
		return w[idx][s];
	}
	if (dp[idx][visit] != -1)
	{
		return dp[idx][visit];
	}
	dp[idx][visit] = INF;
	for (int i = 0; i < n; i++)
	{
		if (w[idx][i] == 0 || visit & (1 << i))
		{
			continue;
		}
		int r = dfs(s, i, visit | (1 << i));
		if (r == INF)
		{
			dp[idx][visit] = min(dp[idx][visit], INF);
		}
		else
		{
			dp[idx][visit] = min(dp[idx][visit], r+w[idx][i]);
		}
	}
	return dp[idx][visit];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> w[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 0, 1);
	return 0;
}

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

문제

문제

출처

ICPC

INF값 때문에요,c#만 이런건지.. 아니면 제가 코드를 잘못짠건지..

powerlsj7 1년 전 1

kokosoko59 1년 전 1

powerlsj7 1년 전 0

powerlsj7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말