선생님 질문이 있습니다ㅜㅜ

Question

저는 코드를 다음과같이 작성을 해보았는데요, 40점이 뜨고, 문제점이 뭔지도 알고 있습니다. 일단 저는 강의를 듣기 전에 코드를 작성해보는 편입니다. 제 코드는 무조건 반드시 1일차의 상담을 선택하는 상황으로 가지가 계속 뻗어나가게만 이루어져 있습니다. 그래서 1일차의 상담을 선택했을때 분기가 모두 끝나는 것도 디버깅으로 확인을 했는데 그 이후 몇시간을 고민했는데도 풀리지 않네요. N의 범위를 넘어가지 않으면서 2일차 강의, 3일차 강의를 선택하는 모든 경우의 수 까지도 고려하고 싶은데 거기서 손을 쓸 수가 없습니다. 이 문제를 해결하려면 제 코드에 어디를 손봐야할까요?ㅜㅜ #include #include #include using namespace std; int* T; int* P; int N; int Tindex = 0; int Total = 0; int totalarray[100]; int cnt = 0; void DFS(int Tindex, int Total) { if (Tindex + T[Tindex] > N) { totalarray[cnt++] = Total; return; } else { DFS(Tindex + T[Tindex], Total + P[Tindex + T[Tindex]]); } } int main() { scanf("%d", &N); T = (int*)malloc(sizeof(int) * (N + 1)); P = (int*)malloc(sizeof(int) * (N + 1)); for (int i = 1; i < N+1; i++) { scanf("%d %d", &T[i], &P[i]); } T[0] = 1; P[0] = 0; DFS(0, 0); //DFS(1, 0); int max = 0; for (int i = 0; i < 100; i++) { if (max < totalarray[i]) { max = totalarray[i]; } } printf("%d", max); }

명랑코딩 · Answer

아주 옛날 질문이지만 공부 겸 수정해 보았습니다. 이렇게 다른 분들의 질문을 보면서 공부하는 것도 재미있네요! 😀 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int* T; int* P; int N; int Tindex = 0; int Total = 0; int totalarray[100]; int cnt = 0; int ans = -2147000000; // Tindex로 넘어가는 값을 상담 후 날짜로 수정 // 예) 1일에 4일 걸리는 상담을 했다면 다음 DFS에는 5가 전달되어서 // 5일 째 상담 데이터를 확인할 수 있도록 void DFS(int Tindex, int Total) { if (Tindex > N + 1) { return; } if (Tindex == N + 1) { if (ans < Total) { ans = Total; } // 시간 초과 이슈로 수정 //totalarray[cnt++] = Total; return; } else { DFS(Tindex + T[Tindex], Total + P[Tindex]); // 2일차, 3일차 강의 고려할 수 있도록 추가 DFS(Tindex + 1, Total); } } int main() { scanf("%d", &N); T = (int*)malloc(sizeof(int) * (N + 1)); P = (int*)malloc(sizeof(int) * (N + 1)); for (int i = 1; i < N + 1; i++) { scanf("%d %d", &T[i], &P[i]); } T[0] = 0; P[0] = 0; DFS(1, 0); // 시간 초과 이슈로 수정 //int max = 0; //for (int i = 0; i < 100; i++) { // if (max < totalarray[i]) { // max = totalarray[i]; // } //} printf("%d", ans); }

김태원 · Answer

안녕하세요^^ 인단 제 영상을 보시고 스스로 문제점을 고쳐보시기 바랍니다.