글 읽기 - 반례 부탁드리겠습니다.(c++)

112224 5년 전 0

맨 처음에 보고 4색 문제인줄 알고 풀었다가 최소의 값을 뽑아내는 문제란 걸 잊어서 틀렸는데

그 부분을 수정하였는데도 틀리네요 ㅠㅠ -> 배열의 인덱스가 잘못되어있는 걸 발견 후 크기를 늘려줬는데 런타임 에러가 발생하였습니다.(98%)

고수님들의 도움과 반례를 바랍니다!

// 01/08 11시경 해결

혹시 비슷하게 짜신 분이 있다면, 색의 갯수를 일괄되게(최대갯수) 돌려주시면 됩니다.

그리고 각 색에 대해서 재귀호출은 지향해주시면 더 좋은 풀이가 될 것 같습니다!

//이전
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

vector<int> a[100001];      //연결여부
int dp[100001][30];

int dfs(int node,int now,int prev,int type)
{
    if(dp[node][now]!=-1)
    return dp[node][now];
    
    int ret=987654321;
    int tmp=now;
    
    for(int i=0;i<a[node].size();i++)
    {
        int t=a[node][i];
        int q=987654321;
        if(t==prev)
        continue;
        for(int j=1;j<=type;j++)
        {
            if(j!=now)
            q=min(q,dfs(t,j,node,type));
        }
        tmp+=q;
    }
    ret=min(ret,tmp);
    return dp[node][now]=ret;
    
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n;
    cin>>n;
    int type=1;
    int cnt=1;
    while(type<n)
    {
        type*=2;
        cnt++;
    }
    memset(dp,-1,sizeof(dp));
    for(int tmp;cin>>tmp;)
    {
        int p;
        cin>>p;
        a[tmp].push_back(p);
        a[p].push_back(tmp);
    }
    int ans=987654321;
    for(int i=1;i<=cnt;i++)
    {
        ans=min(ans,dfs(1,i,0,cnt));
    }

    cout<<ans<<'\n';
}

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

문제

문제

출처

ICPC

반례 부탁드리겠습니다.(c++)

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말