글 읽기 - 11%에서 오답처리가 납니다.

lemonoyaa 1년 전 0

게시판에서 고칠 수 있는 것들은 모두 고쳤는데도

아무리 생각해봐서 바꿔봐도

11%에서 오답처리가 납니다. 어떤 곳이 잘못된 곳인가요?

#include <iostream>
#include <algorithm>
#include <cstring>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 17
#define FINISH ((1<<16)-1)
#define INF 1000000000

using namespace std;

int N;  //도시의 개수 N
int co[MAX_N][MAX_N];  //비용: cost
int memo[FINISH];  //비용 최솟값 메모

void input()
{
    cin >> N;
    LOOP(i, N) {
        LOOP(j, N)
            cin >> co[i][j];
    }
}

void DP(int node, int bm, int sum)  //bitmask, start
{
    if(bm == (FINISH>>16-N) && memo[0]>sum+co[node][1]) {  //다 순회했고 비용이 더 적을 경우 갱신
        if(co[node][1])
            memo[0]=sum+co[node][1];
        return;
    }
    if(memo[bm] && memo[bm]<=sum)  //더 작은 경로로 온 적이 있으며 백
        return;
    memo[bm]=sum;  //경로 최솟값 갱신하기
    
    LOOP(i, N) {
        int next = 1<<i-1;  //다음에 방문할 노드 비트
            
        if((bm&next) || !co[node][i])  //방문한 경우, 또는 길이 없는 경우
            continue;
        else
            DP(i, bm|next, sum+co[node][i]);  //비트마스크 갱신 후 다음 노드로 순회하기
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    memo[0]=INF;
    
    DP(1, 1, 0);
    
    cout << memo[0];
    
    return 0;
}

lemonoyaa 1년 전 0

4
0 7 3 3
7 0 9 2
1 9 0 12
7 7 12 0

답 20

잘못된 출력 21

이 나오네요. 3->7->9->1하면 나오는데 왜 안되는지...

lemonoyaa 1년 전 0

비트마스크가 같다고 해서 모두 같은 경우는 아니였네요. node마다 다르게 메모리제이션했더니 48%?에서 시간 초과가 나네요. 왜 그런거죠..?

#include <iostream>
#include <algorithm>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 17
#define FINISH ((1<<16)-1)
#define INF 1000000000

using namespace std;

int N;  //도시의 개수 N
int co[MAX_N][MAX_N];  //비용: cost
int memo[MAX_N][FINISH];  //비용 최솟값 메모

void input()
{
    cin >> N;
    LOOP(i, N) {
        LOOP(j, N)
            cin >> co[i][j];
    }
}

void DP(int node, int bm, int sum)  //bitmask, start
{
    if(bm == (FINISH>>16-N) && memo[0][0]>sum+co[node][1] && co[node][1]) {  //다 순회했고 비용이 더 적을 경우 갱신
        memo[0][0]=sum+co[node][1];
    if(memo[node][bm] && memo[node][bm]<=sum)  //더 작은 경로로 온 적이 있으면 백
        return;
    memo[node][bm]=sum;  //경로 최솟값 갱신하기
    
    LOOP(i, N) {
        int next = 1<<i-1;  //다음에 방문할 노드 비트
            
        if((bm&next) || !co[node][i])  //방문한 경우, 또는 길이 없는 경우
            continue;
        else
            DP(i, bm|next, sum+co[node][i]);  //비트마스크 갱신 후 다음 노드로 순회하기
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    memo[0][0]=INF;
    DP(1, 1, 0);
    
    cout << memo[0][0];
    
    return 0;
}

lemonoyaa 1년 전 0

생각해보니 다 탐색해서 최솟값을 확신시키면 되는 거였네요

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

문제

문제

출처

ICPC

11%에서 오답처리가 납니다.

lemonoyaa 1년 전 0

lemonoyaa 1년 전 0

lemonoyaa 1년 전 0

lemonoyaa 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말