[AC] 1535 안녕

출처 : https://www.acmicpc.net/problem/1535

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/1535.cpp

문제를 읽어보면 결국 하냐 안하냐 그차이이다. DP와 DFS사이에 고민을 했다. 둘다 방법이 있다. 그런데 이문제에서 주의깊게 봐야할것은 N이 20이다. 즉, DFS로도 충분히 풀 수있다는 것이다.

만약 N값이 30 이상이라면 사실상 DFS로는 가능성이 없으므로  DP로 접근해야한다. 

dp로 푼다면 각 사람별로 기쁨과 소모 체력을 누적시켜가며 최대값을 갱신하는 방식으로 진행해야겠다. 자세한 수식은 더 생각해봐야겠으나 해당문제에서는 DFS로 풀 수 있기 때문에  DFS로 풀었다. 그리고 단순히 선택을 하고 안하고의 차이이므로 전부 계산을 해보면 답이 나온다.

주의해야할점은 체력이 0이 되거나 마이너스가 되면 그어떠한 점수도 얻지 못한다는 점이다.