글 읽기 - dp로 풀었을때 계속 1이 나오는데...

aj4941 4년 전 0

아래 코드와 같이 실행했는데 모든 경우에 대해 계속 1이 나오더군요.

dp[실행 횟수] = A의 최댓값으로 식을 세우고 메모이제이션 방식으로 돌렸는데 답이 안나오는 이유가 뭔지 모르겠습니다. ㅠㅠ

#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
int N;
ll dp[120];
ll solve(ll n, ll a, ll b, ll c) // n : 실행 횟수, a : 화면의 A개수
{								// b : 전체 선택한 개수 c : 버퍼안의 개수
	ll &ret = dp[n];
	if(n == N) return a;
	if(ret != -1) return ret;
	ret = max(solve(n + 1, a + 1, b, c), solve(n + 1, a, a, c));
    // 1) 화면에 A 1개 추가                 2) 화면에 있는 것을 전체 선택
	ret = max(ret, solve(n + 1, a, b, b + c));
             // 3) 전체 선택한 것을 버퍼에 넣기
	ret = max(ret, solve(n + 1, a + c, b, c));
            // 4) 버퍼에 있는 것을 화면에 출력하기
	return ret;
}
int main(void)
{
	memset(dp, -1, sizeof(dp));
	cin >> N;
	cout << solve(0, 0, 0, 0);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp로 풀었을때 계속 1이 나오는데...

aj4941 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말