답은 맞았는데, 이상한 부분이 있어서 질문드려요

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

7-E

해결된 질문

작성

160

http://boj.kr/a12c58c1df11493f8ba78847feffa3b9

선생님, 안녕하세요~

완전탐색(재귀방식)으로 해서 어떻게 답을 맞췄습니다.

처음에는 dp테이블에 동전이 n개일때 경우의 수를 저장해야겠다고 생각하고 코드를 짜보았지만, 뭔가 잘 되지않아

dp[34][34] 이런식으로 남은 w가 n개, h가 m개일때 경우의 수를 저장하게 하는 방식으로 해서 통과하였습니다.

그런데 이상한 점은, 한번 dp방식으로 해서 답을 맞췄으면,

그 다음 입력때도 이전에 저장된 dp테이블에 있는 값을 그대로 이용해서 답을 맞출 수 있을 줄 알았는데,

이전에 저장된 dp테이블을 이용하면 다른 답이 나와서,

입력을 할 때마다 dp테이블을 초기화 해주는 방식을 사용하고 있습니다.

음,, 어떤 부분때문에 이렇게 나오는 걸까요??

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 google님 ㅎㅎ

이러한 경우는 DP의 중간값이 제대로 잘 쌓여지지 않아서 그렇습니다.

예를 들어 목표로 한 DP[5][0]은 잘 쌓였지만 중간에

DP[2][0]은 제대로 쌓이지 않은 것이죠.

이 때문에 DP 5, 0 을 하고 DP 2, 0을 하려고 할 때 미리 쌓여진 배열을 기반으로 처리를 할 때 -> 제대로 안쌓여서 -> 에러가 뜨는 것인데요. (원래는 차근차근 잘 쌓여야 합니다.)

이 방법을 해결하는 방법은 불필요한 로직을 지우며 올바르지 않은 로직을 찾는 방법이 유일합니다.

먼저 불필요한 로직을 지워볼까하는데요.

왜 targetW가 필요할까요? go 함수는 targetW개의 전체 알약 중 restW개의 전체 알약이 남아있고, consumeH개의 반 알약이 사용된 상태에서 가능한 경우의 수를 계산하는 것 같은데요. 현재까지 소모한 전체 알약의 수: consumeW는 targetW - restW로 계산되지만 이부분은 restW와 consumeH으로도 알 수 있지 않을까요?
왜 이러한 로직이 나오나요?

    if (restW > 0)
    {
        if (consumeW == consumeH)
        {
            cnt += go(targetW, restW - 1, consumeH);
        }
        else
        {
            cnt += go(targetW, restW - 1, consumeH);
            cnt += go(targetW, restW, consumeH + 1);
        }
    }

이거는 제가 생각했을 때, 전체 알약을 사용할 수 있는 경우 (restW > 0), 현재까지 소모한 전체 알약 수와 반 알약 수가 같다면 전체 알약 하나를 더 사용하는데요. 왜이게 강제되어야 하나요?

제가 google 님 코드 중에 불필요한 부분을 없애가면서 다시 짜봤습니다.

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

ll dp[31][31];

ll go(ll restW, ll consumeH) {
    if (restW == 0) {
        return 1;
    }

    if (dp[restW][consumeH] != -1) {
        return dp[restW][consumeH];
    } 

    ll cnt = 0;

    if (restW > 0) {
        cnt += go(restW - 1, consumeH + 1);
    }
    if (consumeH > 0) {
        cnt += go(restW, consumeH - 1);
    }

    dp[restW][consumeH] = cnt;
    return cnt;
} 

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

이렇게 하면 초기화 없이 잘 통과 됩니다.

참고 부탁드립니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

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

google_user님께서 질문하신 내용과 유사한 상황에 대해 다른 학생이 질문했던 사례를 찾아드릴 수 있었습니다. 이 과정에서 Dynamic Programming(DP)의 초기화와 상태 정의에 관한 논의가 이루어졌는데, 이는 DP 문제를 해결함에 있어 중요한 점들입니다.

질문하신 문제와 관련하여 DP 테이블을 매번 초기화하는 이유는, 각각의 테스트 케이스는 독립적인 문제로 처리되어야 하기 때문입니다. DP 테이블에 저장된 값은 특정 문제의 상태와 그 때의 최적해를 나타냅니다. 다른 테스트 케이스에 대해서는 이전에 계산된 값을 사용할 수 없는 것이 일반적이며, 이 때문에 새로운 입력이 주어질 때마다 DP 테이블을 초기화하여 새로운 문제에 대한 정확한 해를 구해야 합니다.

답변 참고 링크:
- 7-H 문제 다른방식 풀이 질문 - 이 질문에서는 재귀 방식으로 DP를 구현하는 데 어려움을 겪고 있는 학생에게 DP 배열 초기화와 탑다운(DP) 접근 방식에 대해 설명하고 있습니다.

답변된 내용을 통해 DP 문제에서의 초기화 필요성 및 해결 방법에 대한 실마리를 얻으실 수 있을 것입니다.

무엇보다도, 각 테스트 케이스가 독립적으로 처리되어야 하며, 이를 위해 DP 테이블을 초기화하는 과정이 반드시 필요하다는 점을 이해하는 것이 중요합니다.

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

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

답은 맞았는데, 이상한 부분이 있어서 질문드려요