글 읽기 - 왜 시간초과 뜨는 걸까요?

hyunya 1년 전 0

dp를 0으로 채워서 보내면 맞고, dp를 inf로 채우면 시간초과가 뜹니다. 무엇이 문제인가요?

// 맞은 코드
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f, mxn = 1e5 + 5;
int dp[16][1 << 16], a[16][16], n;
int dfs(int v, int mask)
{
    if(dp[v][mask]){
        return dp[v][mask];
    }
    if(mask == (1 << n) - 1){
        return dp[v][mask] = (a[v][0] ? a[v][0] : inf);
    }
    dp[v][mask] = inf;
    for(int i = 0; i < n; ++i){
        if((mask & (1 << i)) || !a[v][i]){
            continue;
        }
        dp[v][mask] = min(dp[v][mask], dfs(i, mask | (1 << i)) + a[v][i]);
    }
    return dp[v][mask];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
    dp[0][1] = dfs(0, 1);
    cout << (dp[0][1] == inf ? -1 : dp[0][1]);
}

// 시간초과 코드
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f, mxn = 1e5 + 5;
int dp[16][1 << 16], a[16][16], n;
int dfs(int v, int mask)
{
    if(dp[v][mask] != inf){
        return dp[v][mask];
    }
    if(mask == (1 << n) - 1){
        return dp[v][mask] = (a[v][0] ? a[v][0] : inf);
    }
    for(int i = 0; i < n; ++i){
        if((mask & (1 << i)) || !a[v][i]){
            continue;
        }
        dp[v][mask] = min(dp[v][mask], dfs(i, mask | (1 << i)) + a[v][i]);
    }
    return dp[v][mask];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = dfs(0, 1);
    cout << (dp[0][1] == inf ? -1 : dp[0][1]);
}

hyunya 1년 전 0

이해했습니다. 감사합니다!

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

문제

문제

출처

ICPC

왜 시간초과 뜨는 걸까요?

hyunya 1년 전 0

hyunya 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말