회원가입
로그인
Toggle navigation
문제
문제
전체 문제
문제 출처
단계별로 풀어보기
알고리즘 분류
추가된 문제
문제 순위
문제
푼 사람이 한 명인 문제
아무도 못 푼 문제
최근 제출된 문제
최근 풀린 문제
랜덤
출처
ICPC
Olympiad
한국정보올림피아드
한국정보올림피아드시․도지역본선
전국 대학생 프로그래밍 대회 동아리 연합
대학교 대회
카카오 코드 페스티벌
Coder's High
ICPC
Regionals
World Finals
Korea Regional
Africa and the Middle East Regionals
Europe Regionals
Latin America Regionals
North America Regionals
South Pacific Regionals
문제집
대회
2
채점 현황
랭킹
게시판
그룹
더 보기
재채점 기록
블로그
강의
실험실
도움말
BOJ Stack
BOJ Book
전체
공지
자유
질문
오타/오역/요청
게시판 공지
홍보
업데이트
solved.ac
글쓰기
질문 도움말
자주묻는 질문
런타임에러 도움
1949번 - 우수 마을
p_ce1052
4년 전
0
런타임 에러가 나옵니다....ㅠㅠ 틀렸습니다가 될 수 있게 해주세요
#include<iostream> #include<vector> #define IN 0 #define OUT 1 using namespace std; vector<int> residents; //각 마을의 주민 수 (1~n); vector<vector<int> >graph; //각 마을의 연결도 (인접리스트); int dp[2][10001]; //dp[0][i] i번 마을이 포함되었을 때의 최대 주민 수 (자신 아래로만 계산,부모에게 값을 반환); //dp[1][i] i번 마을이 포함되지 않았을 때의 최대 주민 수(자신 아래로만 계산, 부모에게 값을 반환); int init(int n){ for(int i=1; i<=n; i++){ dp[IN][i]=-1; //동적 배열 초기화 dp[OUT][i]=-1; //동적 배열초기화 } } int dfs(int pstate,int parent, int curr){ //부모의 상태와 내 노드 번호 int mystate,res=0; //자신의 상태와 결과값 bool is_leaf=true; //일단 리프노드라고 가정 if(pstate==IN){ //부모가 우수마을이면자신을 포함할 수 없음 mystate=OUT; //나는 우수마을에 포함되지 않는다. if(dp[OUT][curr]!=-1) return dp[OUT][curr]; // 내가 우수마을에 포함되지 않을 때의 최대주민수 //계산한 적 없다면 계산한다 for(int i=0; i<graph[curr].size(); i++){ if(parent!=graph[curr][i]){ //부모는 방문하면 안됨 is_leaf=false; //방문 안된 노드가 있다면 내 자식임 마을은 트리구조이기 때문, 나는 리프노드가 아님 res+=dfs(mystate,curr,graph[curr][i]); // 내 상태를 넘겨주고 최댓값들을 받아옴 } } if(is_leaf){ //내가 리프노드라면 내 상태는 out 이므로 return dp[mystate][curr]=0; //0명으로 표시 후 반환 } else return dp[mystate][curr]=res; //자식이 있다면 자식들로부터 구해온 최댓값의 총합, 나는 out 이므로 포함 안됨 } else{ //부모가 우수마을이 아니라면 나는 우수마을이어도 되고 아니어도 됨. 이 중 최댓값을 반환하자. if(dp[IN][curr]==-1){ //내가 우수마을일 때의 최댓값이 저장되있지 않다면 mystate=IN; //내 상태는 우수마을 for(int i=0; i<graph[curr].size(); i++){ if(parent!=graph[curr][i]){ is_leaf=false; //자식이 있다면 리프노드가 아님 res+=dfs(mystate,curr,graph[curr][i]); //자식들로부터 내 상태에 대한 최댓값들을 구해와서 더함 } } //내가 리프노드라면 내 주민 수만 반환, 아니라면 내 주민 수 + 자식들로부터의 최대 주민 수의 합 반환 dp[IN][curr]=residents[curr]+(is_leaf?0:res); } if(dp[OUT][curr]==-1){ //내가 우수마을이 아닐 때의 최댓값이 저장되있지 않다면 mystate=OUT; //나는 우수마을이 아니다 res=0; for(int i=0; i<graph[curr].size(); i++){ if(parent!=graph[curr][i]){ is_leaf=false; //나는 리프노드가 아님 res+=dfs(mystate,curr,graph[curr][i]); //내 상태를 주고 자식들에게서 총합을 구함 } } dp[OUT][curr]=(is_leaf?0:res); //내가 리프노드라면 우수마을이 아니므로 0명,리프노드가 아니라면 ret을 반환 } int res=max(dp[IN][curr],dp[OUT][curr]); return res; //부모가 우수마을이 아니라면 이 중 최댓값을 반환하자. } } int solve(int root){ //루트마을의 부모는 없지만 부모의 상태가 out이라고 가정하면 나는 들어가도 되고 안들어가도 됨 //이 중 최댓값을 반환하면 답이다. return dfs(OUT,0,root); //부모는 없으니 0번이라고 가정 } int main(){ ios_base::sync_with_stdio(false); int n,a,b; cin>>n; init(n); residents=vector<int>(n+1); graph=vector<vector<int> >(n+1); for(int i=1; i<=n; i++) cin>>residents[i]; for(int i=1; i<n; i++){ cin>>a>>b; graph[a].push_back(b); graph[b].push_back(a); } cout<<solve(1); //아무 노드나 루트로 정해서 답을 계산하자. 트리 형태이므로 루트가 무엇이든 상관 없음. return 0; }
wjddydgns99
4년 전
1
11줄에 int 형의 함수를 void 로 바꾸어야 합니다. 맞은 코드네요.
72줄에 반환형이 없어요.
p_ce1052
4년 전
0
감사합니다 dev c++ 쓰는데 거기서는 컴파일 잘 되고 예제도 잘 돌아갔어서 저런 이유일줄은... 컴파일러마다 또 다를 수 있나 보군요 긴 코드 보시느라 고생하셨습니다
댓글을 작성하려면
로그인
해야 합니다.
p_ce1052 4년 전