7-V 바텀업 질문

안녕하세요 Raerae님 ㅎㅎ

먼저 답변이 늦은 점 죄송합니다.

처음에는 Raerae님 코드 기반으로 하려다가 잘 안되서 1차원배열로는 어떻게 풀어야할까... 하면서

여러번 시도하다 결국 답안을 찾은 것 같습니다.

이 코드가 1차원배열로 푸는 방법입니다.

#include <bits/stdc++.h>
using namespace std;  

int n, k, dp[100001], dp2[100001], t1, t2, p1, p2;

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

    cin >> n >> k;
    //0 부터 시작해야하니.
    dp[0] = 1;
    for (int i=0; i<n; ++i) {
        cin >> t1 >> p1 >> t2 >> p2;
        // 해당 경우의 수에서 하나밖에 못쓰는 냅색을 생각. 
        for(int j = k; j >= 0; j--){
            if(dp[j]){
                if(j + t1 <= k) dp[j + t1] = max(dp[j + t1], dp[j] + p1);
                if(j + t2 <= k) dp[j + t2] = max(dp[j + t2], dp[j] + p2);
                // 모금액을 순차적으로 모집하는 것이기 때문에 
                // 이번에 모금액을 갱신했다면 해당 인덱스의 모금액은 초기화를 둬서
                // 현재 인덱스에서의 선택지를 처리한 후에는 해당 상태를 더 이상 사용하지 않도록 합니다.
                // 즉, 중복 갱신을 막는다.  
                dp[j] = 0;
            }
        } 
    }
    // 처음 시작한 1을 빼준다. 
    cout << *max_element(dp,dp+k+1)-1; 
    

    return 0;
}

냅색을 응용한 DP라고 보시면 됩니다.

주석 달았으니 참고 부탁드립니다. ㅎㅎ

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

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

감사합니다.

강사 큰돌 올림. 

안녕하세요, 인프런 AI 인턴입니다.

님의 질문은 프로그래밍 문제 해결과 관련된 구체적인 코딩 문제에 대한 것으로 보입니다. 제가 제공한 정보는 인프런에 관한 일반적인 정보에 관한 것이기 때문에, 직접적인 코딩 문제 해결에 대해 응답할 수 없습니다. 하지만, 문제 해결에 도움이 될 수 있는 몇 가지 제안을 드리겠습니다.

• 문제 접근 방식을 다시 한번 검토해보시고, 바텀업 방식을 구현하는 데 있어 놓친 부분은 없는지 확인해보세요.
  
• 해당 문제와 유사한 문제들을 찾아보고, 다른 사람들이 어떻게 접근하여 해결했는지 참고해보세요.
  
• 문제에 대한 힌트나 해결 방법을 제공하는 온라인 포럼이나 커뮤니티에서 질문해 보세요.
  

코딩 문제를 해결할 때는 문제를 체계적으로 분석하고, 다양한 시도를 하는 것이 중요합니다. 계속해서 도전하시고, 다양한 자료를 참고하시면서 해결 방법을 찾으시길 바랍니다.

원하는 답변을 찾지 못하셨나요? 그럼 원하시는 정보를 얻을 수 있는 더 구체적인 채널을 찾아보실 것을 권장드립니다. 예를 들어, 인프런 내에서 관련 강좌의 질문 & 답변 섹션을 활용하셔도 좋을 것 같습니다.

도움이 될 수 있기를 바라며, 문제 해결을 위한 여정에서 최선을 다하시길 응원합니다.