프로그래머스 코드 챌린지 11월!

이번에도 운이 좋게 4번문제가 좋아 하는 스타일이여서 풀 수 있었다..!!

3번은 문제를 잘못 각 부분 집합들이 같은수를 공통으로 포함해야 하는건데 잘못읽고 풀다가 시간을 많이 날려 먹었고 using namespace std;를 제출할때 빼서 max()에서 계속 모호하다고 빠꾸를 먹었다.. 이런적이 처음이여서 쫌 당황 했다. 

 

4번은 트리 dp였는데 한 노드에서 2개의 간선이 뻗어 나오면 문제가 없고 한 노드에서 3개의 간선이 빠져 나오면 입력과 출력이 달라야 하고 입력도 출력도 아닌 간선은 무조건 곧은 직선으로만 이뤄 져야 한다는 아이디어 에서 출발했다. 

dfs를 돌려 리프 노드로 root 로 설정하고 간뒤 각 노드마다  root와의 dep을 저장해 주고 dfs dp를 했다. 리프에서 해당 지점까지 일직석으로만 올경우 최대 길이 문제에서 요구하는 부분 트리를 만족하는 경우 최대 노드 수를 각각 저장하며 올라왔다. 정답은 각 dfs에서 return 을 하기전 해당 노드를 정답에 넣을경우 최대 몇개를 넣을수 있는지를 기준으로 했다. 간선이 2개인거는 쉽고 3개 이상이라면 해당 지점에서 root까지를 직선으로 보고 나머지 두 간선을 부분 노드들로 생각해 이어줬다.