U E D R , A S I H C RSS

POLY/김태진

��������/POLY

  • ��������
  • DP�� ������.
    • ������ ���� ��고, X개�� ������ ��� 경����
      • X-1개(���� ������ ���고) + ���� ���� 1개 , X-2개 + ���� 2개, ... , 1개 + ���� X-1개, ���� X개 �� �갤 �� ����.
      • �, ���� ������ ��� ��� ���� ������ 개��� �개�� ������, ���� 개�� ���������� 개���� �� ���������� ������ 경���� ��� ������기 ����.
      • (������ ���� 3개, �������� 2개(그 ���� ������)�� 경���� " ���� + �������� - 1 ", �� 4개�� 경��� �기고, �� 곱��.
        • ��기까 �� ���� ���� DP ������ ����고, 그�� �� ������ ��고 ������. ������ ������������ 3���� for��과 ���� ��, ���� ������ ��� �게 �� ���.

//
//  main.cpp
//  Algospot_normal
//
//  Created by Jereneal Kim on 13. 8. 15..
//  Copyright (c) 2013�� Jereneal Kim. All rights reserved.
//

#include <iostream>
using namespace std;
int dp[101][101] = {0};
int main(int argc, const char * argv[])
{
	int i,j,level,n,T;
	dp[1][1]=1;
	for(level=2;level<=100;level++){
		for(i=1;i<level;i++){
			for(j=1;j+i<=level;j++){
				dp[level][i] %= 10000000;
				dp[level][i] += (i+j-1)*dp[level-i][j];
			}
		}
		dp[level][i]=1;
	}
	scanf("%d",&T);
	for(int iter=0;iter<T;iter++){
		scanf("%d",&n);
		int sum=0;
		for(i=1;i<=n;i++){
			sum=(sum+dp[n][i])%10000000;
		}
		printf("%d\n",sum);
	}
	return 0;
}

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:58
Processing time 0.0312 sec