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

(追記) (追記ここまで)

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

14946번 - 누가 크리스마스 소리를 내었는가

Green55 7년 전 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);
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

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

Green55 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말