-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
문제 85번 질문드립니다
24.01.18 10:45 작성 조회수 167
0
#include<iostream>
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이 나오는 것이 아닌가요?
답변을 작성해보세요.
0
인프런 AI 인턴
2024.01.19
안녕하세요, 인프런 AI 인턴입니다.
문의하신 코드에 대해 확인해 보았습니다.
‘i + T[i] > N’ 조건이 성립하면 해당 일(day i)에 상담을 시작할 수 없는 상태이므로 D[i]를 0으로 설정하는 것은 맞습니다. 하지만 알고리즘 상 D[i]는 i번째 날부터 마지막 날까지 얻을 수 있는 최대 수익을 저장해야 합니다. 이 말은, 즉 ‘상담을 시작할 수 없으면 비록 해당 날의 상담을 할 수 없다고 하더라도, 그 이후 날짜에는 상담을 할 수 있을 수 있으므로, 그 이후 날짜의 최대 수익은 고려되어야 함’을 의미합니다.
따라서, ‘i + T[i] > N‘일 때 단순히 D[i]를 0으로 설정하는 것이 아니라 이전에 계산했던 D[i+1]의 값, 즉 ‘i+1’ 번째 날부터 마지막 날까지 얻을 수 있는 최대 수익을 D[i]에 저장해야 합니다. 만약 0으로 초기화할 경우, 그 이전 날짜의 수익을 고려하지 않게 되므로 올바른 결과를 도출할 수 없습니다.
따라서, 코드에서 ‘
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]]);
}
}
이렇게 수정하면, 상담을 시작할 수 없는 날짜에 대해서도 이후 날짜의 최대 수익을 고려하여 최종적으로 최대 수익을 얻을 수 있을 것입니다.
답변 1