인프런 커뮤니티 질문&답변
작성한 질문수
선생님 질문이 있습니다ㅜㅜ
작성
·
228
0
저는 코드를 다음과같이 작성을 해보았는데요,
40점이 뜨고, 문제점이 뭔지도 알고 있습니다.
일단 저는 강의를 듣기 전에 코드를 작성해보는 편입니다.
제 코드는 무조건 반드시 1일차의 상담을 선택하는 상황으로 가지가 계속 뻗어나가게만 이루어져 있습니다.
그래서 1일차의 상담을 선택했을때 분기가 모두 끝나는 것도 디버깅으로 확인을 했는데 그 이후 몇시간을 고민했는데도 풀리지 않네요.
N의 범위를 넘어가지 않으면서
2일차 강의, 3일차 강의를 선택하는 모든 경우의 수 까지도 고려하고 싶은데 거기서 손을 쓸 수가 없습니다.
이 문제를 해결하려면 제 코드에 어디를 손봐야할까요?ㅜㅜ
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
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);
}답변 2
0
아주 옛날 질문이지만 공부 겸 수정해 보았습니다. 이렇게 다른 분들의 질문을 보면서 공부하는 것도 재미있네요! 😀
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
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);
}0
