퇴사

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

삼성 코딩 테스트 기출 문제이다.

BFS로 풀었다. 계속 틀렸다고 나온다.

그래서 DFS로 다시 풀었다.

DP 로도 풀 수 있다고 한다.

예시

다음의 예시로 설명하겠다.

BFS 오답 풀이

위의 그림과 같이, 시작 날짜를 다르게 하여 BFS를 모두 실행한다.

더 이상 자식 노드가 없을 때가 마지막이므로, 이 때 이익 합을 계산한다.

BFS 오답 코드

DFS 정답 코드