글 읽기 - 리그 오브 레전설 반례가 뭔지 궁금합니다.

busyhuman 4년 전 0

조합 DP를 이용해서 풀었는데 다른 방법이나 반례를 알려주시면 감사하겠습니다.

#include <iostream>
using namespace std;
#define mod 1000000007
int n, b;
long long dp[10001][101];
long long dfs(int i, int j){
	if(i == j || j == 0) return dp[i][j] = 1;
	if(dp[i][j]) return dp[i][j];
	return dp[i][j] = ( (dfs(i-1,j-1) % mod) + (dfs(i-1, j) % mod) ) % mod;
}
int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> b;
	long long ans = 1;
	for(int i=1;i<=n/b;i++){
		ans += dfs(n-i*(b-1),i);
		ans %= mod;
	}
	cout << ans;
}

sait2000 4년 전 0

dfs에서 j의 범위가 101을 한참 넘어가는 것 같은데요

in:
250 2

out:
841382049

busyhuman 4년 전 0

@sait2000 말씀해주신거랑 long long을 int로 바꾸니 되네요. 감사합니다

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

문제

문제

출처

ICPC

리그 오브 레전설 반례가 뭔지 궁금합니다.

busyhuman 4년 전 0

sait2000 4년 전 0

busyhuman 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말