문제 85번 질문드립니다

Question

#include using namespace std; int T[16]; int P[16]; int D[16]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("input.txt", "r", stdin); int N; cin >> N; for (int i = 0; i < N; i++) { cin >> T[i] >> P[i]; } for (int i = N - 1; i >= 0; i--) { if (i + T[i] > N) D[i] = 0; else { D[i] = max(D[i + 1], P[i] + D[i + T[i]]); } } cout << D[0]; } 여기서 초기화할 때 왜 0으로 하면 14프로까지 갔다가 틀렸습니다가 나오는지 잘 모르겠습니다 'i + T[i] > N' 다음 조건이 성립하면 항상 점화식의 값이 0이 나오는 것이 아닌가요?

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. 문의하신 코드에 대해 확인해 보았습니다. &lsquo; i + T[i] > N &rsquo; 조건이 성립하면 해당 일(day i )에 상담을 시작할 수 없는 상태이므로 D[i] 를 0으로 설정하는 것은 맞습니다. 하지만 알고리즘 상 D[i] 는 i 번째 날부터 마지막 날까지 얻을 수 있는 최대 수익을 저장해야 합니다. 이 말은, 즉 &lsquo;상담을 시작할 수 없으면 비록 해당 날의 상담을 할 수 없다고 하더라도, 그 이후 날짜에는 상담을 할 수 있을 수 있으므로, 그 이후 날짜의 최대 수익은 고려되어야 함&rsquo;을 의미합니다. 따라서, &lsquo; i + T[i] > N &lsquo;일 때 단순히 D[i] 를 0으로 설정하는 것이 아니라 이전에 계산했던 D[i+1] 의 값, 즉 &lsquo; i+1 &rsquo; 번째 날부터 마지막 날까지 얻을 수 있는 최대 수익을 D[i] 에 저장해야 합니다. 만약 0으로 초기화할 경우, 그 이전 날짜의 수익을 고려하지 않게 되므로 올바른 결과를 도출할 수 없습니다. 따라서, 코드에서 &lsquo; if (i + T[i] > N) D[i] = 0; 이 부분을 if (i + T[i] > N) D[i] = D[i + 1]; 로 수정해야 합니다. D[i + 1] 은 i+1 날짜부터 계산된 최대 수익 값입니다. 이렇게 변경하면 i 번째 날에 상담을 할 수 없다면 i+1 번째 날부터의 최대 수익을 D[i] 에 저장하게 됩니다. 변경 후 코드는 다음과 같습니다. for (int i = N - 1; i >= 0; i--) { if (i + T[i] > N) D[i] = D[i + 1]; else { D[i] = max(D[i + 1], P[i] + D[i + T[i]]); } } 이렇게 수정하면, 상담을 시작할 수 없는 날짜에 대해서도 이후 날짜의 최대 수익을 고려하여 최종적으로 최대 수익을 얻을 수 있을 것입니다.