7103

static int N, sels[5];
static int table[32767 + 1];

static int __solution(int s, int v, int cnt)
{
	if (v == N)
	{
		//해당 수를 이루는 조합을 확인 할 수 있다.
		return 1;
	}

	if (cnt <= 4)
	{
		int ret = 0, ret1;
		for (int i = s; i <= N; i++)
		{
			int val = v + i * i;
			if (val > N)
				break;
			else if (val <= N)
			{
				if (val < N)
				{
					//해당 수를 이루는 조합을 확인 할 수 있다.
					table[val] += 1;
				}

				sels[cnt] = i; //선택 옵션
				ret1 = __solution(i, val, cnt + 1);
				if (ret1)
					ret += ret1;
				else
					sels[cnt] = 0; //선택 옵션
			}
		}
		return ret;
	}
	else
		return 0;
}

static int solution(void)
{
	scanf("%d", &N);
	int &ret = table[N];

	if (!ret)
		ret = __solution(1, 0, 1);

	return ret;
}

static void init_table(void)
{
	N = 32767;
	int ret = __solution(1, 0, 1);
	table[N] = ret;
}

라그랑주 네제곱수라는 정리와 연관되는 문제이다.

 

최근 여러 문제들을 재귀로 풀어나가면서 이 문제도 역시 재귀로 접근을 해보았다.

여러 삽질을 거치다가 원하는 출력이 제대로 나와서 테스트를 돌려보았지만 제한시간 초과가 발생하였다.

사실 알고리즘 문제 특성 상 해당 수를 이루는 네개의 제곱수들을 굳이 알 필요는 없었다.

그러나 풀이방향이 한번 잡혀버리고 나면 다른 방식으로 사고를 잘 하지 못하는 터라 제한시간 초과를 어떻게 해야 할 지 잘 몰랐다.

그래서 그냥 정답 코드 들 중 하나를 참조하였다. 여기서 나는 한동안 잊고있던 동적계획법이 사용 된 것을 볼 수 있었다.

사실 예전에는 문제를 풀 때 먼저 동적계획법을 고려하던 시기가 있었는데, 최근 재귀로만 문제를 해결하려 한 터라 이를 고려하지 못한 것이다. 앞으로는 편협한 사고방식을 좀 버려야 할 것 같다.

 

어쨌든 위 코드의 동작 방식은 아래와 같다.

4개의 제곱수 들 중 첫번째 제곱수는 1부터 확인 해 나가는 것이다.

두번째 제곱수는 첫번째 제곱수가 사용하는 값 이상, 세번째는 두번째 제곱수가 사용하는 값 이상을 확인 해 나가면서 타겟으로 하는 값을 만들 수 있는지 보는 것이다.

이 와 중에 4개 이하의 제곱수로 이루어진 값이 만들어 질 수 있다. 이를 미리 마련한 답안 테이블에 등록하는 것이다.