nyoj 743 복잡도 (배열 조합)
복잡도
시간 제한:
1000ms | 메모리 제한:
65535 KB
난이도:
3
묘사
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
for(k=j+1;k<=n;k++)
operation;
operation이 모두 몇 번이나 실행되었는지 아십니까?
입력
m과 n을 입력하면 m가 for 순환의 층수이고 n은 for의 n이다.
(n, m<=2000), 입력은 n==0과 m==0으로 끝납니다.
출력
출력 operation 실행 횟수 (입력 결과mod 1009)
샘플 입력
2 3
1 3
2 4
0 0
샘플 출력
3
3
6분석:
처음에 제목의 뜻을 이해하지 못했는데 알고리즘의 복잡도가 이런 알고리즘이 아니기 때문에 분석한 후에 알 수 있듯이 제목의 뜻은 m층의 순환이 있고 층마다 n개의 수가 있다. 순환 초기 값에서 알 수 있듯이 층마다 수가 같지 않다. 즉, n개의 수에서 m개의 다른 수를 고르면 이런 조합이 몇 가지가 있는지 바로 c(n, m)이다. n과 m는 최대 2000이기 때문에 저장할 수 없기 때문에 수조로 미리 표를 작성하면 OK이다.
시계를 치려면 배열 조합 c(n,m)=c(n-1,m)+c(n-1,m-1)를 알아야 한다. 약간 양휘삼각형 같다.
#include<stdio.h>
#include<string.h>
int dp[2010][2010];
int main()
{
int i,j,m,n;
memset(dp,0,sizeof(dp));
for(i=1; i<2001; i++)// ， i 0 ， i i 1
dp[i][0]=dp[i][i]=1;
for(i=1; i<2001; i++)// ， (i,j)=c(i-1,j-1)+c(i-1,j)
for(j=i-1; j>0; j--)
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%1009;//
while(scanf("%d%d",&m,&n)&&m+n)
{
printf("%d
",dp[n][m]); //
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
