백트래킹1 SWEA 2112 보호필름 백트래킹 가지치기를 잘 해야 시간초과가 나지 않는다 한 열이 실패하면 그 경우는 무조건 실패다 → return false 한 열에서 k개 이상이 되면 그 열은 성공이다 → continue loop 해서 다음 열 탐색으로 넘어가자 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다 알고리즘 1. 어떤 행에 약품을 투여할지 조합으로 정한다 (0개 ~h-1개) - h-1개까지 해서 안 되면 h개 투여해야하는 거니까 예외처리로 출력해준다 - 새로운 dfs마다 memcpy를 해준다 2. 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다 3. 조합을 돌리면서 재귀 전 insert, 재귀 후 delete로 약품 투여를 처리해준.. 2020. 5. 20. 이전 1 다음