DP 개념강의 자두나무 질문

작성한 질문수 5

0

안녕하세요 인서님 ㅎㅎ

지금 해설 강의에 있는 코드를 보시면 다음과 같이 되어있습니다.

이코드로 하시면 인서님이 생각하신 대로 나오게 됩니다.

#include<bits/stdc++.h>
using namespace std;
int dp[1004][2][34], n, m, b[1004];

int go(int idx, int tree, int cnt){
	if(cnt < 0) return -1e9;
	if(idx == n) return 0;
    int &ret = dp[idx][tree][cnt];
    if(~ret) return ret;  
    return ret = max(go(idx + 1, tree^1, cnt - 1), go(idx + 1, tree, cnt)) + (tree == b[idx] - 1); 
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> b[i]; 
    cout << max(go(0, 1, m - 1), go(0, 0, m)) << '\n'; 
    return 0;
}

그러나 해설코드 제공 교안을 보면 2개의 코드를 제공하는 데 그 중 하나가 잘못 된 것 같습니다.

이부분은 오늘내로 수정하도록 하겠습니다.

혼란을 드려 죄송합니다.

감사합니다.

0

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

자두나무 문제에서 결과가 다르게 나오는 것은 기저 조건과 이동이 최적화되지 않았을 가능성이 있습니다. 강사님께서 해당 문제를 설명하신 부분을 더 정확하게 이해하려면 몇 가지 관련 질문과 설명을 참고하시면 도움이 될 것 같습니다.

1. 2240_자두나무_기저사례 질문: 여기 게시물에서는 기저 사례와 관련한 코드의 조건이 다루어지고 있습니다. 이는 반환값 조정에서 매우 중요합니다.

2. 2240번 자두나무 질문있씁니다!: 자두나무 문제에서 입력 값을 다르게 처리함에 있어 어떻게 max() 함수가 활용되는지에 대한 설명이 있습니다.

기저 조건 설정에서, 배열 경계를 벗어날 때의 처리와 최적 이동 횟수를 다 사용하지 않았을 때의 처리 값이 매우 중요합니다. 만약 음수의 결과가 나왔다면, 이는 주로 이동 가능 횟수가 모자라거나 조건 충족이 안 되어 발생하는 일입니다.

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