글 읽기 - 이 문제에 관련된 알고리즘 질문입니다. 관심부탁드립니다.

vjerksen 6년 전 0

Tree + Dynamic Programming 이라고 생각하고 문제를 해결하려 했습니다.

1. 간선을 입력 받는다.

2. 그래프를 통해 트리를 구현한다.

3. value라는 구조체를 선언해서 색의 종류에 따라 값을 저장한다.

4. "dp[now][color][val] : 현재 now번인 노드에서 color인 색을 가지며, val만큼의 값을 가지고 있을 때의 가지 수" 라고 생각하고 solve함수를 구현

혹시 제가 접근한 방법 자체가 오류인지, 구현 과정에서 오류를 범했는 지에 대해서, 저의 턱없이 모라잔 지식으로는 알 길이 없습니다. 이미 이 문제를 해결하신 분들, 알고리즘 분야의 고수님들, 이 문제에 관심이 있으신 분들 모두에게 도움을 청합니다.

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<cmath>
using namespace std;

typedef struct{
    int red,green,blue;
}RGB;
int V,Q,K;
vector<int> graph[1003],tree[1003];
bool visit[1003];
RGB value[1003];
int dp[1003][3][13];

void makeTree(int here){
    visit[here]=true;
    for(int i=0;i<graph[here].size();i++){
        int there = graph[here][i];
        if(!visit[there]){
            tree[here].push_back(there);
            makeTree(there);
        }
    }
}
int solve(int now,int color,int val){
    if(tree[now].size()==0){
        if(val%K)
            return 0;
        else
            return 1;
    }
    int& ret = dp[now][color][val];
    if(ret!=-1) return ret;

    ret=0;
    for(int i=0;i<tree[now].size();i++){
        int next = tree[now][i];
        if(color==1){ // green
            ret+=(solve(next,0,(val+value[next].red)%K)%Q+solve(next,2,(val+value[next].blue)%K)%Q)%Q;
        }
        else if(color==2){  // blue
            ret+=solve(next,1,(val+value[next].green)%K)%Q;
        }
        else{   // red
            ret+=(solve(next,0,(val+value[next].red)%K)%Q+solve(next,1,(val+value[next].green)%K)%Q+solve(next,2,(val+value[next].blue)%K)%Q)%Q;
        }
    }
    return ret%Q;
}
int main(){
    std::ios::sync_with_stdio(false);
    memset(dp,-1,sizeof(dp));
    cin >> V >> Q >> K;
    for(int i=0;i<V-1;i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    makeTree(1);
    for(int i=1;i<=V;i++){
        int r,g,b;
        cin >> r >> g >> b;
        value[i].red = r;
        value[i].green = g;
        value[i].blue = b;
    }
    cout << (solve(1,0,value[1].red)%Q + solve(1,1,value[1].green)%Q + solve(1,2,value[1].blue)%Q) % Q;
    return 0;
}

solveit 6년 전 0

red 부분에서 부모 노드가 빨간색인데 자식 노드가 파란색일 수 있을까요.

문제에 나와있는걸로 봤을때 파란색은 인접 노드의 색깔이 초록색이어야만 하는것 같은데요

vjerksen 6년 전 0

@solveit

RR RG RB : 현재 색이 red일 때, 다음 소켓에 연결할 수 있는 색은 red와 green.

GR GG GB : 현재 색이 green일 때, 다음 소켓에 연결할 수 있는 색은 red와 blue.

BR BG BB : 현재 색이 blue일 때, 다음 소켓에 연결할 수 있는 색은 green.

이렇게 고치면 예제 2번의 정답이 나오지 않습니다. 혹시 제가 놓치고 있는 부분이 있는 건가요?

for(int i=0;i<tree[now].size();i++){
        int next = tree[now][i];
        if(color==1){ // green
            ret+=(solve(next,0,(val+value[next].red)%K)%Q+solve(next,2,(val+value[next].blue)%K)%Q)%Q;
        }
        else if(color==2){  // blue
            ret+=solve(next,1,(val+value[next].green)%K)%Q;
        }
        else{   // red
            ret+=(solve(next,0,(val+value[next].red)%K)%Q+solve(next,1,(val+value[next].green)%K)%Q)%Q;
        }
    }

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

문제

문제

출처

ICPC

이 문제에 관련된 알고리즘 질문입니다. 관심부탁드립니다.

vjerksen 6년 전 0

solveit 6년 전 0

vjerksen 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말