인프런 커뮤니티 질문&답변

DFS 풀이는 시간초과가 발생하는 이유가 궁금합니다.

DFS 풀이는 시간초과가 발생하기 때문에 DP로 풀어야하는건가요?

이에 대한 설명은 없어서 질문드립니다.

DFS 시간초과 코드는 다음과 같았습니다.

struct Work {
	int s, e;
	int score;
};
int n, m, r;
vector<Work> schedule;
int result = 0;

bool compare(Work a, Work b) {
        return a.s < b.s;
}

void dfs(int now, int start, int score) {
	if (now >= n) {
		result = max(result, score);
		return;
	}
	result = max(result, score);

	for (int i = start; i < m; i++) {
		if (schedule[i].s < now) continue;
		dfs(schedule[i].e + r, i + 1, score + schedule[i].score);
	}
}

int main() {
	cin >> n >> m >> r;
	for (int i = 0; i < m; i++) {
		int s, e, score;
		cin >> s >> e >> score;
		schedule.push_back({ s,e,score });
	}
	sort(schedule.begin(), schedule.end(), compare);
	dfs(0, 0, 0);
	cout << result;
	return 0;
}