imported>jereneal20 at 12:12, 15 August 2013

2013-08-15T12:12:57Z

← Older revision		Revision as of 12:12, 15 August 2013
Line 6:		Line 6:
	** 이때, 제일 위층을 제외한 것의 제일 위층의 개수가 몇개인지 중요한데, 최상층 개수와 두번째층의 개수에 의해 폴리오미노를 만족하는 경우의 수가 세분화되기 때문이다.		** 이때, 제일 위층을 제외한 것의 제일 위층의 개수가 몇개인지 중요한데, 최상층 개수와 두번째층의 개수에 의해 폴리오미노를 만족하는 경우의 수가 세분화되기 때문이다.
	** (예를들어 최상층 3개, 두번째층 2개(그 아래층은 상관없음)인 경우는 " 최상층 + 두번째층 - 1 ", 즉 4개의 경우가 생기고, 이를 곱해야한다.		** (예를들어 최상층 3개, 두번째층 2개(그 아래층은 상관없음)인 경우는 " 최상층 + 두번째층 - 1 ", 즉 4개의 경우가 생기고, 이를 곱해야한다.
	*** 여기까지 이해를 했다면 직접 DP 점화식을 만들어보고, 그렇지 않다면 코드를 보고 이해해보려고 노력해보자.		*** 여기까지 이해를 했다면 직접 DP 점화식을 만들어보고, 그렇지 않다면 코드를 보고 이해해보려고 노력해보자. 실제로 유의미한 코드는 3번째 for문과 점화식 한줄, 총 두줄 뿐이라는 것을 알게 될 것이다.
	//		//
	// main.cpp		// main.cpp
Line 25:		Line 25:
	for(i=1;i<level;i++){		for(i=1;i<level;i++){
	for(j=1;j+i<=level;j++){		for(j=1;j+i<=level;j++){
	dp[level][i] = (dp[level][i]+(i+j-1)*dp[level-i][j]~~)%10000000~~;		dp[level][i] %= 10000000;
			dp[level][i] += (i+j-1)*dp[level-i][j];
	}		}
	}		}

imported>jereneal20 at 12:11, 15 August 2013

2013-08-15T12:11:05Z

New page

= 폴리오미노/POLY =
* [http://www.algospot.com/judge/problem/read/POLY 폴리오미노]
* DP를 이용한 문제.
** 가로줄을 층이라 치고, X개로 만드는 것의 경우는
** X-1개(제일 위층을 제외하고) + 제일 위층 1개 , X-2개 + 최상층 2개, ... , 1개 + 최상층 X-1개, 최상층 X개 로 쪼갤 수 있다.
** 이때, 제일 위층을 제외한 것의 제일 위층의 개수가 몇개인지 중요한데, 최상층 개수와 두번째층의 개수에 의해 폴리오미노를 만족하는 경우의 수가 세분화되기 때문이다.
** (예를들어 최상층 3개, 두번째층 2개(그 아래층은 상관없음)인 경우는 " 최상층 + 두번째층 - 1 ", 즉 4개의 경우가 생기고, 이를 곱해야한다.
*** 여기까지 이해를 했다면 직접 DP 점화식을 만들어보고, 그렇지 않다면 코드를 보고 이해해보려고 노력해보자.
//
// 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] = (dp[level][i]+(i+j-1)*dp[level-i][j])%10000000;
}
}
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;
}

POLY/김태진 - Revision history

imported>jereneal20 at 12:12, 15 August 2013

imported>jereneal20 at 12:11, 15 August 2013