글 읽기 - 틀린 코드가 왜 틀렸는지ㅠ..

dwhylee 7년 전 0

처음에 중복순열? 로 생각해서 comb 로 풀었더니 틀려서 고칠 방법을 못 찾아서.

dp로 짜기위해서 수를 계산해보니

0 1 2 3 4 5.. 200
0 1 3 6 10 15 20000
0 1 4 10 20 35 1353400

이런 형태가 나오는걸 알았고 dp로 풀었습니다.

중복순열의 식으로는 왜 틀리는지 궁금하네요 ㅜㅜ 결과값이 다르게 나오는걸 봐선

곱하기/ 나누기 할때 문제가 생기는 것 같은 짐작은 되지만, 정확히는 모르겠어서 질문 올립니다.

#pragma warning(disable:4996)
#include <cstdio>

int dp[201], N, K;
int main(){
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= K; i++)	 dp[i] = i;
	for (int i = 1; i < N; i++){
		for (int j = 1; j <= K; j++)
			dp[j] = (dp[j] + dp[j - 1]) % 1000000000;
	}
	printf("%d", dp[K] % 1000000000);
}

/*
int N, K;
using namespace std;
long long comb(int n, int r){
	long long result = 1;
	int chek = n / 2;
	if (chek < r) r = n - r;
	for (int i = 0; i < r; i++){
		result *= (n - i);
		result = (result / (i + 1)) % 1000000000;
	}
	return result;
}
int main(){
	scanf("%d%d", &N, &K);
	printf("%lld",(comb(N + K - 1, N))%1000000000);
}
*/

tols91 7년 전 0

음.. 나누기는 모듈러 연산 할 때 다르게 해야 한다고 알고있어요

dwhylee 7년 전 0

@tols91 다르게 라는 것은 어떻게 하는건가요?ㅁ?

qja0950 7년 전 0

예를들어 12를 2로 나누는 과정에서 MOD = 10일때를 생각해보면,

실제로는 12/2 = 6이므로 6이 나와야하지만,

위의 코드같이 진행하면 (12%10)/2 = 1이 나오게 됩니다.

더 설명을 덧붙이자면, MOD M에 대해 생각할 때

gcd(a, M) = 1인 경우, a^phi(M) == 1 (mod M)을 이용하면 (오일러의 정리)

b / a 하는 과정을 b * a^{(phi(M) - 1)} 로 바꾸어서 해주시면 됩니다.

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

문제

문제

출처

ICPC

틀린 코드가 왜 틀렸는지ㅠ..

dwhylee 7년 전 0

tols91 7년 전 0

dwhylee 7년 전 0

qja0950 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말