백준 4673번

BOJ 4673번 : 셀프넘버

생각해내는 것도 만만치 않았지만

구현도 어려움이 좀 있었다

일단 이 문제는 d(n) 이라는 함수를 알맞게 표현하는 것이 먼저이다

d(n) = a(10^3+1)+ b(10^2+1) + c(10^1+1) + d(10^0+1) 로 표현하고 나면

그 다음은 이 d(n) 을 다 찾아주면 된다

이때 문제는 d(n) 결과값만을 배열로 저장해서 1~10000 의 숫자와 비교하는 식으로 하면 중간중간 걸림돌이 많이 생긴다 (중복된 값, 정렬, 비교 등)

그래서, 크기가 10000짜리인 배열을 만들고

d(n) 의 결과값을 인덱스로 이용해 표시하면 된다

예컨대, char arr[10000] = 0 을 생성하고

d(n) 에 해당하는 인덱스의 원소 값을 1로 바꿔주는 식의 방법이다

아래의 코드는 동적할당으로 작성되었으나

Visual Studio 에서 배열 크기로 인한 스택 오버플로우가 발생해서 동적할당으로 수정한 것이지

스택만 충분하다면 (또는 VS에서 스택 크기를 좀 늘려 놓으면)

배열로 작성해도 충분하다

#include <stdio.h>
#include <stdlib.h>

typedef char* (FP)();

char* d();

int main()
{

	char* arr = (char*)malloc(sizeof(int) * 10000);
	memset(arr, 0, sizeof(int) * 10000);

	arr[0] = 1;
	arr[2] = 1;
	arr[4] = 1;
	arr[6] = 1;
	arr[8] = 1;

	for (int a = 0; a < 10; a++)
	{
		for (int b = 0; b < 10; b++)
		{
			for (int c = 0; c < 10; c++)
			{
				for (int d = 0; d < 10; d++)
				{
					int num = a * 1001 + b * 101 + c * 11 + d * 2;

					if (num <= 10000)
					{
						arr[num] = 1;
					}
				}
			}
		}
	}

	for (int i = 0; i < 10000; i++)
	{
		if (arr[i] == 0)
			printf("%d\n", i);
	}

	free(arr);

	return 0;
}