7-T 초기조건 관련 질문드립니다.

안녕하세요, 늘 좋은 강의 감사드립니다.

다름이 아니라 해당 문제를 풀면서 go(idx, sum) 함수의 초기값을 어떻게 보내는지에 따라 오답처리가 되어 문의드립니다.

제가 처음 짠 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 987654321;

ll dp[104][24];
int arr[104];
int n;
int target;

ll go(int idx, int sum){
    if(idx==n-1){
        if(sum==arr[idx])return 1;
        else return 0;
    }

    ll &ret = dp[idx][sum];
    if(ret!=-1) return ret;

    ret = 0;
    if(sum+arr[idx] <=20){
        ret += go(idx+1, sum+arr[idx]);
    }
    if(sum-arr[idx]>=0){
        ret += go(idx+1, sum-arr[idx]);
    }

    return ret;

}

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

    memset(dp, -1, sizeof(dp));

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    target = arr[n-1];

    cout << go(0,0) << '\n';

    return 0;
}

위와 같이 go(0,0)으로 한 경우 오답처리가 되었습니다.

반면 go(1, arr[0])로 시작한 경우 정답처리가 됩니다.

제가 생각하기에 go 함수 내 조건문에 따라 음수값은 처리하여

go(1, arr[0])와 차이가 없다고 생각했는데 어디서 문제인거지 알 수 있을까요?

안녕하세요, 인프런 AI 인턴입니다. 김우영님.

질문하신 내용은 Dynamic Programming을 사용한 문제에서 초기화 조건 및 함수 호출 시점의 초기 값에 관한 것입니다. go(0,0)와 go(1, arr[0])로 시작했을 때 오답과 정답이 나오는 이유는, 초기 상태에 따라 탐색할 수 있는 경로가 달라지기 때문입니다.

구체적으로 설명드리자면,

go(0, 0)로 시작: 이 초기 조건은 문제의 첫 번째 수를 더하거나 빼는 과정 없이 시작하기 때문에, 예제 내에서 주어진 조건을 빠뜨릴 위험이 있습니다. 따라서 문제 조건에 맞지 않아서 오답으로 판단될 수 있습니다.
go(1, arr[0])로 시작: 이 초기 조건은 처음부터 배열의 첫 번째 요소를 고려하여 합의 초기값을 가져가므로 문제의 모든 조건을 고려할 수 있게 됩니다. 각 단계에서 올바른 상태를 유지하여 이후 조건 확인 및 연산을 진행할 수 있습니다.

따라서, 문제의 맥락에 대한 더 깊은 이해가 필요하며, 초기값 설정에서 연산 과정이 문제에서 지정한 범위나 조건을 항상 만족하는지, 경계 조건을 잘 다루고 있는지를 확인하는 것이 중요합니다.

관련 질문 URL을 참고하시며 더 깊이 이해하실 수 있습니다:
- 7-T 5557번 1학년 문제 질문입니다.
- 7-T 5557 1학년

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

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