[BOJ C++] 5021 왕위 계승

https://www.acmicpc.net/problem/5021

5021번: 왕위 계승

 

 

문제 이해

나라를 세운 건국자가 있고 그 자식들이 표현이 되어있습니다. 해당 자식은 한세대를 거칠 수록 부모의 혈통의 1/2을 이어 받게 됩니다.

만약 건국자와 건국자와 관련  없는 인물 사이에서 태어난 인물의 혈통은 1/2가 되는 것이고, 1/2의 혈통을 가진 인물과 아무런 관계없는 인물 사이에서 아이가 태어나면 1/4 + 0 으로 1/4의 혈통을 가진 아이가 태어나게 되는 것입니다.

건국자와 아이와 부모의 관계가 주어질 때 자신이 왕위를 계승해야 한다고 주장하는 인물 중 가장 높은 혈통을 가진 인물을 찾는 문제였습니다.

 

 

입출력 조건

시간 제한은 1초, 3명의 인물 씩 총 50줄 주어질 수 있으므로 최대 인물의 수는 150명 정도가 가능했습니다.

또 주어지는 자식조건이 50줄이라는 뜻과 같으므로 depth는 최대 50이라고 생각하였습니다.

 

 

풀이

첫번째로 문제를 풀때 너무 쉽게 생각했었습니다.map에 <string,long long>으로 잡아주고 건국자는 2^50을 넣어줬습니다.(최대 depth가 50이였기에 자연수 단위로 해결하기 위해) 이후 입력을 받음과 동시에 해당 인물이 이미 나왔던 인물인지를 확인하고 자식에게는 부모의 절반의 숫자를 더 더해주는 식으로 문제를 해결하였습니다. 우연찮게 테스트케이스도 모두 맞아 떨어지며 문제를 해결한 것 처럼 보였지만 게속 5%에서 틀렸다고 하였습니다...

 

알고보니, 뒤늦게 나오는 정보에서 앞선 인물의 정보가 나오는 경우가 있었습니다. 그래서 앞선 방법은 바로 폐기처분 해버렸습니당

먼저 입력을 다 받고, 인물을 정점으로, 관계를 간선으로 생각하기로 했습니다. 그렇게 되었을 때 자식에게는 2개의 in_degree가 추가가 되게 되고 in_degree가 0인 부모 노드부터 처리하며 해당 부모의 value의 1/2만큼 씩 자식에게 추가되도록 코드를 구현해 주었습니다.

알고보니 위상정렬 문제였던 것입니다..!

 

 

에러 및 느낀 점

역시 처음에는 방법이 잘못되어 많은 에러를 발생시켰습니다.

 

두번째로 제대로 된 방법을 이용했을 때는, 최대 50줄이 설명됨으로 단순히 최대 50명까지 나올 수 있구나 라고 생각하여 배열의 크기가 부족한 문제가 있었습니다.

 

또 두번째는 테스트 용으로 2^10으로 잡아뒀던 것을 고치지 않아 틀렸습니다가 발생했었습니다...^^;;

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/5021_%EC%99%95%EC%9C%84%20%EA%B3%84%EC%8A%B9.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.