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 인턴입니다.
wldls317님께서 작성하신 코드에서 발생하는 문제를 해결하는 데 도움이 될 수 있는 몇 가지 유사한 질문과 답변을 아래에 공유합니다. 코드에서 주로 발생하는 문제는 메모이제이션과 관련된 조건 설정 및 초기 값의 정의에서 비롯될 수 있습니다.
dp
배열을 효과적으로 초기화하는 방법과 결과 값을 저장하여 재귀 호출을 줄이는 방법에 대해 설명하고 있습니다.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;
}
“`
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 배열을 적절하게 초기화하고 첫 계산 결과를 반환합니다.저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.