인프런 커뮤니티 질문&답변

안녕하세요 동훈님 ㅎㅎ

메모이제이션 체크하는 로직이 잘못된 것 같습니다.

    if (ret > 0) return ret;

ret이 계산되어있냐? 라고 했을 때 양수면 계산된걸까요? (이 때문에 메모이제이션이 제대로 안걸려서 -> 시간초과인 것 같습니다.)

처음에 우리가 초기화를 -1e9로 하기 때문에 해당 값이 아니라면 -> 계산이 된 것임이 자명합니다. 해당 부분에 맞춰 로직을 짜면 됩니다.

제가 좀 다듬어봤는데요. 참고 부탁드립니다.

#include <bits/stdc++.h>
 

using namespace std;
typedef long long ll;

int N, K;
pair<int, int> A[101][2];
int dp[101][100001];

int go(int idx, int time) {
    if (idx >= N) {
        return 0;
    } 
    int &ret = dp[idx][time];
    if (ret != -1e9) return ret;   
    if (A[idx][0].first + time <= K) {
        ret = max(ret, go(idx + 1, A[idx][0].first + time) + A[idx][0].second);
    }

    if (A[idx][1].first + time <= K) {
        ret = max(ret, go(idx + 1, A[idx][1].first + time) + A[idx][1].second);
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;
    fill(&dp[0][0], &dp[0][0] + 101 * 100001, -1e9); 

    for (int i = 0; i < N; i++) {
        int n1, n2, m1, m2;
        cin >> n1 >> n2 >> m1 >> m2;
        A[i][0] = {n1, n2};
        A[i][1] = {m1, m2};
    }

    cout << go(0, 0);

    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.