PKU 3132. Sum of Different primes. AC get -_-

#include 
#include 

using namespace std;

set tool;
set::iterator sit;
int tot, n, k, cnt, checker[15][1121];

void maketool()
{
	int i;
	bool isPrime;

	tool.insert(2);
	tool.insert(3);

	for (i = 5; i <= 1120; i += 2)
	{
		isPrime = true;
		for (sit = tool.begin(); sit != tool.end(); sit++)
		{
			if (i % *(sit) == 0)
			{
				isPrime = false;
				break;
			}
		}

		if (isPrime)
		{
			tool.insert(i);
		}
	}
}

int main()
{
	int i, j, k, l;
	set::iterator dit;
	maketool();

	while (cin >> n >> k)
	{
		if (n == 0 && k == 0)
		{
			break;
		}

		memset(checker, 0, sizeof(checker));
		checker[0][0] = 1;

		for(j = 0, dit = tool.begin(); j < tool.size() && *(dit) <= n; j++, dit++)
		{
			for(i = k; i >= 1; i--)
			{
				for(l = n; l >= *(dit); l--)
				{
					checker[i][l] += checker[i - 1][l - *(dit)];
				}
			}
		}
		cout << checker[k][n] << endl;
	}
}

이런 쒯

짜증나게 더럽네 ㄱ-

고생 더럽게 했음요.

처음엔 소수를 tool 셋을 이용해 DFS로 탐색했으나,

100 5만 해도 거의 안드로메다급 탐색시간을 보여줘서 GG

그리고 다시 곰곰히 생각해보니 k가 커봐야 14라는 점을 기억해내고, 저런 알고리즘을 짜내봤습니다.

checker의 k, n번째 있는게 답이고,

소수의 리스트를 전부 싹다 더해보고 비벼보고 하면서 checker 배열에 가능한 갯수들을 체크해

넣어보되, 그 탐색 범위를 소수 내에서, k개 골라서, n보다 작고 현재 검사중인 소수보다 큰 놈을 이용해서

뭐 이거 설명하기도 더럽네 -_-

여튼 그렇게 비비고 볶고 해서 맵을 만들어서(자기 자신만으로 답인거, 2개 합해서 되는거, 3개 해서 되는거, .... k개 해서 되는거) 

로 최종 결산해 답을 가져오는 코드입니다.

진짜 더럽다 ㄱ-