반례

10
1 2
2 3
2 4
4 6
4 5
6 7
6 8
8 9
8 10

답: 4

출력: 5

깊이 기준으로 홀수 혹은 짝수를 전부 고르는 방법은 전부 전파 되기는 하겠지만 최소 횟수라고 장담할 수는 없습니다.

더 쉬운 반례:

6

1 2

2 3

2 4

4 5

4 6

답:2

출력:3

작성하신 코드는 트리의 아래쪽이 어떻게 되어있는 상관없이 현재 상태만 보고 답을 결정합니다.

뒤 쪽의 상태와 관계없이 항상 정답으로 간다는 보장이 있는 선택지가 있어야만 이러한 알고리즘, 즉 그리디 알고리즘을 적용 할 수 있습니다.

문제를 푸실 때 그리디 보단 동적계획법을 먼저 고려해보시는게 좋을 것 같습니다.

동적계획법을 한번 생각하고 나면, 이 그리디 알고리즘이 합당한가?를 생각할 때 도움이 되기 때문입니다.

바쁜시간내어 도움주셔서 감사합니다 선배님 ㅠㅠ 반례주신걸 그려보고 나서야 왜 안되는지 알게되었네요 조언도 숙지하겠습니다!!