nyoj 743 복잡도 (배열 조합)

1476 단어

복잡도


시간 제한:
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; }

좋은 웹페이지 즐겨찾기