-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
질문 있습니다
24.04.02 12:54 작성 조회수 54
0
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int maximum=-2147000000;
vector<pair<int, int>> A;
void DFS(int day, int now_day, int income);
int main(){
cin >> n;
for(int i=1; i<=n; i++){
int a, b;
cin >> a >> b;
A.push_back(make_pair(a, b));
}
for(int i=1; i<=A.size(); i++){
DFS(A[i].first, i, 0);
}
cout << maximum;
}
void DFS(int day, int now_day, int income){
if(day>n){
if(income>maximum) maximum=income;
return;
}
else if(day==n){
income+=A[now_day].second;
if(income>maximum) maximum=income;
return;
}
else{
income+=A[now_day].second;
for(int i=day+1; i<=n; i++){
DFS(day+A[i].first, i, income);
}
}
}
해당 코드로는 알맞는 정답이 출력되지 않는데, 그 이유를 모르겠습니ㅏㄷ.
답변을 작성해보세요.
0
인프런 AI 인턴
2024.04.04
안녕하세요, 인프런 AI 인턴입니다.
해당 코드의 주요 문제는 DFS
함수의 탐색 조건과 인덱스 관련 로직에 있습니다. 주어진 코드는 상담할 수 있는 날짜를 초과해서 탐색이 진행될 수 있으며, A
벡터의 인덱스 접근 방식에 오류가 있습니다.
벡터
A
는 0부터 인덱싱이 시작되므로,main
함수에서DFS
를 호출할 때i-1
을 사용해야 합니다. 즉,DFS(A[i-1].first, i-1, 0);
로 수정해야 합니다.DFS
함수의 첫 번째if
조건문에서,day>n
이 아니라now_day+day > n
으로 수정해야 합니다. 상담을 시작하는 날짜(now_day
)와 상담을 완료하는데 걸리는 시간(day
)을 합친 값이n
을 초과할 경우 탐색을 종료해야 하는데, 코드에서는 현재 날짜만 고려하고 있습니다.또한,
DFS
함수 내에서 다음 상담을 선택할 때day+A[i].first
대신day+A[i-1].first
를 사용해야 합니다. 그리고DFS
호출시,i
대신i-1
을 사용해야 합니다.
정리하면, 코드에서 주요 수정 사항은 다음과 같습니다:
main
함수에서DFS
호출 부분:DFS(A[i-1].first, i-1, 0);
DFS
함수 내 조건 및 재귀 호출 부분: 조건 수정과 인덱스 접근 방식 수정
이러한 수정사항을 반영하면 코드가 올바르게 작동할 가능성이 높아집니다. 다만, 코드 전체의 취지를 고려해 필요한 추가 수정사항이 있을 수 있으니 참고하여 코드를 검토해 보시기 바랍니다.
답변 1