글 읽기 - 이 방법은 안되는 걸까요??

kioio5 6년 전 0

매번 1의 박스를 놓는다고 생각하는거랑 비슷하게 생각했습니다.

매번 놓는 박스를 가장 작은 높이의 박스라고 생각하고?

박스를 놓기 때문에

맨왼쪽에 놓는경우는 l + 1이 될것이고.

맨오른쪽에 놓는경우는 r + 1이 될것입니다

그 외의 것은 l과 r이 값이 변하지 않고

if (n >= 2) {
ret = (ll)f(n + 1, l, r) * (n - 1);
ret %= MOD;
}

라고생각했습니다.

n-1인 이유는 박스가 n개가 있다고 생각했을떄

그 사이에 작은 박스를 넣을 경우가 n -1 개라고 생각했기 때문입니당.

탈출조건은

if (n == N) {
if (l == L && r == R) return 1;
else return 0;
}

해당 높이에서 인풋받은 것 값과 같을 떄 리턴 1 그외는 리턴 0을 하게 했습니다

왜 안되는 걸까요? 어디서 오류를 범하는 것일까요?

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>

#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5

using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;

int L, R, N;
int dp[101][101][101];

int f(int n, int l, int r) {
	if (n == N) {
		if (l == L && r == R) return 1;
		else return 0;
	}

	int &ret = dp[n][l][r];
	if (ret != -1) return ret;
	ret = 0;

	if (n >= 2) {
		ret = (ll)f(n + 1, l, r) * (n - 1);
		ret %= MOD;
	}
	
	ret += f(n + 1, l + 1, r) + f(n + 1, l, r + 1);
	ret %= MOD;

	return ret;
}

int main() {
	cin >> N >> L >> R;

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

	cout << f(1, 1, 1);

	return 0;
}

irishw 6년 전 0

재귀함수 인자가 좀 꼬인것 같습니다

for로 일단 구현해 보시면 쉽게구현가능할거에요.

방향은 맞습니다

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

문제

문제

출처

ICPC

이 방법은 안되는 걸까요??

kioio5 6년 전 0

irishw 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말