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

wldls317님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-E

7-e 코드 질문 있습니다!

24.09.13 19:19 작성

·

21

0

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

dp의 첫 인덱스에 알약 복용한 일차 / 두번째에는 0일시, 해당 일차에 1/2 꺼냈을 때 / 1일 시 해당 일차에 1 꺼냈을 때 이렇게 세팅하였는데, 결과가 잘 안나옵니다. 혹시 제 코드에 어떤 문제점이 있는지 알 수 있을까요?

#include <bits/stdc++.h>

using namespace std;

int dp[64][2];  // dp[day][0] -> 남은 반쪽 약의 개수, dp[day][1] -> 남은 하나 약의 개수
int c;

int move(int day, int tA, int tB) {
    if (tA <= 0 && tB <= 0) return 0;  // 기저 조건
    if (dp[day][0] != -1 && dp[day][1] != -1) return dp[day][0] + dp[day][1];  // 이미 계산된 상태 반환

    int ret1 = 0;
    int ret2 = 0;

    // 반쪽 약을 먹는 경우
    if (tA > 0) {
        ret1 += move(day + 1, tA - 1, tB);
    }

    // 하나짜리 약을 꺼내서 반쪽 약을 추가하는 경우
    if (tB > 0) {
        ret2 += move(day + 1, tA + 1, tB - 1);
    }

    // dp 배열에 결과 저장
    dp[day][0] = ret1;
    dp[day][1] = ret2;

    return ret1 + ret2;
}

int main() {
    cin >> c;
    memset(dp, -1, sizeof(dp));  // dp 배열 초기화
    
    dp[1][0]=1;
    dp[1][1]=c-1; // 하나를 쪼개서 반이 된 상태임 

    // 첫째날은 반쪽 약 1개, 하나 약 c-1개로 시작
    cout << move(1, 1, c - 1) << "\n";

    return 0;
}

답변 2

0

큰돌님의 프로필 이미지
큰돌
지식공유자

2024. 09. 14. 14:07

안녕하세요 ㅎㅎ

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

테스트케이스를 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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

인프런 AI 인턴님의 프로필 이미지

2024. 09. 13. 19:21

안녕하세요, 인프런 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 배열을 적절하게 초기화하고 첫 계산 결과를 반환합니다.

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

wldls317님의 프로필 이미지

작성한 질문수

질문하기