백준 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;
}
Author And Source
이 문제에 관하여(백준 4673번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@charlieppark/백준-4673번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)