[BOJ] C++ 14501: 퇴사 - 백트래킹과 재귀

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제를 분석하다 가장 먼저 떠오른 풀이는 백트래킹이었다. N이 최대 15이므로 최대 가능한 상담이 2^15개로 계산된다. 그리고 각 경우의 수당 이익을 계산하는 것과 백트래킹 하는 과정은 상수 시간이 소모될 것 같아서 가능하다 판단하고 백트래킹으로 구현을 시작했다. 구현이 조금 막막하게 느껴질 수 있는데, 일단 모든 경우의 수를 판단해야 한다. 대충 트리를 만들어보자면 이런 형태를 띤다. 트리대로 구현하면서 가지치기를 해주면 될 것 같다. 이런 느낌의 완전탐색은 재귀로 구현하면 비교적 쉽다. 재귀로 구현하고 재귀식 내부에서 백트래킹을 해주는 걸로 하고 구현해 보자. 재귀를 구현할 땐 아래의 세 부분을..

2023.12.18