코드업 4046 학급편성 medium 누적해서 메모리저장

최근 경남중학교에서는 기초학력 미달학생들을 구제하기 위한 효율적인 수업 운영을 위하여 소인수 학급 편성 방법을 고민하고 있다.

 

이를테면, 대상학생이 3명이면 (1명+1명+1명), (2명+1명), (3명)으로 편성하는 세 가지 방법을 검토해 볼 수 있다. 또, 대상학생이 5명이면 (1+1+1+1+1), (2+1+1+1), (2+2+1), (3+1+1), (3+2), (4+1), (5)로 편성하는 일곱 가지 방법을 검토해 볼 수 있다.

 

여기서 수업의 품질을 고려하여 학급당 최대학생수를 통제하기로 하였다. 예컨대,대상학생이 5명이고 학급당 최대학생수가 3명이면, (1+1+1+1+1), (2+1+1+1), (2+2+1), (3+1+1), (3+2)로 다섯 가지 방법이 도출된다.

큰 데이터가 입력으로 들어오므로 방법의 수에 123456789로 나눈 나머지를 출력하시오.

입력

자연수 N과 M이 공백으로 구분되어 입력된다. (1≤N≤1,300, 1≤M≤1,300)

출력

편성방법의 수를 123456789로 나눈 나머지를 출력한다.

입력 예시   예시 복사

5 3

출력 예시

5

 

#include "iostream"
using namespace std;

unsigned int dp[5001][5001];
unsigned int sumup[1001][1001];

int main(void)
{
	unsigned int n, m;
	cin >> n >> m; // 5 3

	unsigned int sum, cha;
	dp[1][1] = 1;
	sumup[1][1] = 1;
	for (unsigned int i = 1; i <= n; i++) // 4 5
	{
		dp[i][i] = 1;
		sumup[i][i] = 1;
		for (unsigned int j = 1; j <= i; j++) // 3까지  2~ 4 i == 3 j = 1 2 3
		{
			sum = 0;
			cha = i - j;
			dp[i][j] = (sumup[i - j][j] + dp[i][j]) % 123456789; // d+ [7][6] = sumup[1][6]
			sumup[i][j] = (sumup[i][j - 1] + dp[i][j]) % 123456789;
			for (unsigned int k = i + 1; k <= m; k++)
				sumup[i][k] = sumup[i][i];
		}

	}
	// for (unsigned int i = 1; i <= n; i++)
	// {
	// 	for (unsigned int j = 1; j <= m; j++)
	// 		cout << dp[i][j] << " ";
	// 	cout <<"\n";
	// // }
	// for (unsigned int i = 1; i <= n; i++)
	// {
	// 	for (unsigned int j = 1; j <= m; j++)
	// 		cout << sumup[i][j] << " ";
	// 	cout <<"\n";
	// }
	sum = 0;
	for (unsigned int i = 1; i <= m; i++)
	{
		sum += dp[n][i] % 123456789;
	}
	cout << sum % 123456789;
}

예시로는 8 6 하면 20이 나오기 

 

8 6 같은 작은 수들을 잘 나온다

 

처음에는 % 123456789를 잘못 두어서 틀리는 줄 알았는데 

 

그게 아니라 누적합을 일일이 계산하면서 생겼던 문제였던것 

#include "iostream"
using namespace std;

unsigned int dp[5001][5001];
unsigned int sumup[2000][2000];

int main(void)
{
	unsigned int n, m;
	cin >> n >> m;

	unsigned int sum, cha;
	dp[1][1] = 1;
	sumup[1][1] = 1;
	for (unsigned int i = 1; i <= n; i++)
	{
		dp[i][i] = 1;
		sumup[i][i] = 1;
		for (unsigned int j = 1; j <= i; j++)
		{
			sum = 0;
			cha = i - j;
			dp[i][j] = (sumup[i - j][j] + dp[i][j] ) ;
			sumup[i][j] = (sumup[i][j - 1] + dp[i][j]) % 123456789;
			for (unsigned int k = i + 1; k <= m; k++)
				sumup[i][k] = sumup[i][i];
		}

	}
	sum = 0;
	cout << sumup[n][m];
}

직접 만들었으니 바로 써먹었다. 

 

그러니 통과!