글 읽기 - DP로 접근했는데 맞는 접근인지 궁금합니다

Green55 6년 전 0

트리를 구성하는거까지는 만들었는데 막상 solve 함수를 어떻게 작성해야 할지 모르겠습니다.

노드부터 시작해서 자식들을 재귀호출하며 순회하면 된다고 생각했는데,

sum의 값이 모든 리프에 흩어져 있어서 이걸 어떻게 모아야 할지 모르겠습니다.

아예 DP로 접근한 것이 틀린걸까요?

#include<bits/stdc++.h>
using namespace std;
// R, G -> R -> R, G
// R, B -> G -> R, B
// G -> B -> G
const int R=0, G=1, B=2;
int v,q,k,cost[1000][3],parent[1000],dp[1000][3][10];
bool visit[1000];
vector<int> adj[1000], child[1000];
void find_child(int here){
	visit[here] = true;
	for(int &there : adj[here])
		if(!visit[there]){
			child[here].push_back(there);
			find_child(there);
		}
}
int solve(int here, int before, int sum){
	//현재 here 소켓을 끼울 차례이고
	//저번에 끼운 소켓의 색이 before 이고
	//현재까지 끼운 소켓의 비용의 합의 나머지가 sum
    for(int there : child[here])
        if(before==R) //(there,R)와 (there,G) 호출
        else if(before==G) //(there,R)와 (there,B) 호출
        else if(before==B) //(there,G) 호출
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dp,-1,sizeof(dp));
	cin >> v >> q >> k;
	for(int i=1; i<v; ++i){
		int a,b;
		cin >> a >> b;
		--a, --b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=0; i<v; ++i)
		cin >> cost[i][R] >> cost[i][G] >> cost[i][B];
	find_child(0);
	memset(dp,-1,sizeof(dp));
	cout << solve(0,G,0) + solve(0,B,0);
}

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

문제

문제

출처

ICPC

DP로 접근했는데 맞는 접근인지 궁금합니다

Green55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말