글 읽기 - 문제는 풀었는데 범위관련 질문합니다 (c언어)

skajd1 4년 전 0

주석 별표 입력해놓은 곳에서 다른분들 보면 초기값을 N - (입력받은 N의 자릿수*9 ) 로 설정하시던데 그 부분이 도저히 이해가 안갑니다..

저는 이거때문에 실행시간이 좀 오래걸린거같습니다.

#include <stdio.h>

int d(int n)
{
	return n + n%10 + (n%100 - n%10)/10 + (n%1000-n%100)/100 + (n%10000-n%1000)/1000 + (n%100000-n%10000)/10000 + (n%1000000-n%100000)/100000 +n/1000000; // d(n) 정의 
}

int main()
{

	int N;
	scanf("%d",&N);
	for(int i=1;i<=N;i++) ///// ** 이부분
	{
		if(d(i)==N)
		{
			printf("%d",i);
			goto a;
		}
	}
	printf("0");
	a:
	
	return 0;
}

rasauq1122 4년 전 1

초기값을 그렇게 설정하면, D(초기값)이 항상 N보다 작다는 것을 알 수 있습니다.

a = N - (ceil(log10(N)+1))*9 // ceil(x)는 x보다 작지 않은 가장 작은 정수

D(a) = a + S(a) // S(x) 는 x의 각 자리수의 합

= N - (ceil(log10(N)+1))*9 + S(a)

이때, S(a) < (ceil(log10(N)+1))*9 이므로

D(a) < N

rasauq1122 4년 전 1

ceil 이 아니라 floor 입니다 ㅠ 헷갈렸네요

skajd1 4년 전 0

풀어서 보니까 당연한거였네요.. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제는 풀었는데 범위관련 질문합니다 (c언어)

skajd1 4년 전 0

rasauq1122 4년 전 1

rasauq1122 4년 전 1

skajd1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말