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

안녕하세요 ㅎㅎ

코드리뷰는 다음과 같습니다.

테스트케이스를 while루프통해서 해야하는데 해당 부분이 안되어있습니다. + 상태값이 올바르게 안들어가있습니다. 이 문제에서 중요한 점은 ta, tb 입니다. 한개짜리 반개짜리의 수인 것이죠. 그러나 DP배열을 보면 day, {0 or 1} 로 되어있어 올바르게 메모이제이션이 되지 않는 코드입니다.

제가 수강생님 코드를 다듬어봤는데요.ㅎㅎ 참고부탁드립니다.

#include <bits/stdc++.h>

using namespace std;

long long dp[31][31];  
long long move(int tA, int tB) { 
    if (tA == 0 && tB == 0) return 1;
 
    if (dp[tA][tB] != -1) return dp[tA][tB];

    long long ret = 0;
 
    if (tA > 0) ret += move(tA - 1, tB);
 
    if (tB > 0) ret += move(tA + 1, tB - 1);
 
    dp[tA][tB] = ret;

    return ret;
}

int main() {
    while (true) {
        int N;
        cin >> N;  
        if (N == 0) break;   
        memset(dp, -1, sizeof(dp));
 
        cout << move(0, N) << "\n";
    }

    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

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

wldls317님께서 작성하신 코드에서 발생하는 문제를 해결하는 데 도움이 될 수 있는 몇 가지 유사한 질문과 답변을 아래에 공유합니다. 코드에서 주로 발생하는 문제는 메모이제이션과 관련된 조건 설정 및 초기 값의 정의에서 비롯될 수 있습니다.

유사한 질문 및 답변

1. 7-S 시간초과 질문드립니다 !!

   • 이 질문에서는 재귀 호출의 효율성을 높이기 위해 메모이제이션을 어떻게 활용하는지 설명하고 있습니다. 이는 wldls317님의 코드에서도 동일하게 중요한 부분입니다.
     
   • 중요한 부분: dp 배열을 효과적으로 초기화하는 방법과 결과 값을 저장하여 재귀 호출을 줄이는 방법에 대해 설명하고 있습니다.
     
   • 강사님 답변 요약:
     ”`cpp
     #include
     using namespace std;
     

   string S;
   bool DP[2505][2505];
   int DP2[2505];
   #define INF 987654321

   void fill_palindrome_dp() {
   int n = S.size();
   for (int i = 0; i < n; i++) {
   DP[i][i] = true;
   if (i < n - 1 && S[i] == S[i + 1])
   DP[i][i + 1] = true;
   }

    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            DP[i][j] = S[i] == S[j] && DP[i + 1][j - 1];
        }
    }
   

   }

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

    cin >> S;
   
   
    fill_palindrome_dp();
   
   
    fill(DP2, DP2 + 2505, INF);
    DP2[0] = 0;
   
   
    int n = S.size();
    for (int here = 0; here < n; here++) {
        if (DP[0][here]) {
            DP2[here] = 0;
        }
        for (int i = 0; i < here; i++) {
            if (DP[i + 1][here]) {
                DP2[here] = min(DP2[here], DP2[i] + 1);
            }
        }
    }
   
   
    cout << DP2[n - 1] + 1;
    return 0;
   

   }
   “`

2. 7-D 질문드려요 (메모이제이션)

   • 설명 내용에서 메모이제이션의 적용 방법과 그 이유에 대해 상세히 설명하고 있습니다. 이 부분을 참고하시면 wldls317님의 코드에서 메모이제이션을 어떻게 효과적으로 적용할 수 있을지 이해하는 데 도움이 될 것입니다.
     
   • 강사님 답변 요약:
     

     
     if (dp[n] != -1) return dp[n]; 
     dp[n] = fib(n-1, dp) + fib(n-2, dp);
     return dp[n];
     

     
     

코드 수정 제안

wldls317님의 코드에서도 비슷한 접근 방식을 적용해 보겠습니다:

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

int dp[64][64]; // [남은 반쪽 약의 개수][남은 하나 약의 개수]

int move(int h, int w) {
    if (h == 0 && w == 0) return 1; // 모든 약을 다 먹은 경우

    if (dp[h][w] != -1) return dp[h][w]; // 이미 계산된 경우 값 반환

    dp[h][w] = 0;

    // 반쪽 약을 먹는 경우
    if (h > 0) {
        dp[h][w] += move(h - 1, w);
    }

    // 하나짜리 약을 먹는 경우
    if (w > 0) {
        dp[h][w] += move(h + 1, w - 1);
    }

    return dp[h][w];
}

int main() {
    int c;
    cin >> c;

    memset(dp, -1, sizeof(dp)); // dp 배열 초기화

    cout << move(0, c) << "\n"; // 시작은 반쪽 약 0개, 하나 약 c개

    return 0;
}

요약 설명

• 메모이제이션을 활용하여 이미 계산된 결과를 재사용합니다.
  
• 입력값 c에 따라 dp 배열을 적절하게 초기화하고 첫 계산 결과를 반환합니다.
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.