글 읽기 - (C++) 시간 초과의 이유를 잘 모르겠습니다.

bear1704 3년 전 0

안녕하세요.

문제에 대한 풀이는

count 변수를 통해 제시된 입력이 몇 자리 수인지 알아낸 다음, 생성자가 될 수 있는 최소 조건을 정하였습니다.

int num = N - 9 * count; 를 통하여

N = abc + a + b + c이므로 abc가 될 수 있는 최소값을 구하는 것입니다.

그리고, ret을 통해 num + 1의 자리 + 10의 자리....를 구하여 만약 이 값이 N과 같다면 루프를 종료하게 만들었습니다.

시간초과를 벗어난 적이 없어 이러한 로직이 틀릴지는 잘 모르겠지만, 더 이상 수행시간을 줄일 수 있는 방법을 잘 모르겠습니다.

문제는 4%에서 시간초과가 됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int main()
{

	int N = 0;
	scanf("%d", &N);

	int copy_N= N;
	int count = 0;

	while (copy_N != 0)
	{
		copy_N /= 10;
		count++;
	}

	int ret = 0;
	int num = N - 9 * count;

	while (ret != N)
	{
		int temp = num;

		ret = 0;
		ret += num;
		
		while (temp != 0)
		{
			ret += temp % 10;
			temp /= 10;
		}

		num++;
	}

	printf("%d", num - 1);

	return 0;

}

luniro 3년 전 1

입력이 9일 때 어떻게 되나요?

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

문제

문제

출처

ICPC

(C++) 시간 초과의 이유를 잘 모르겠습니다.

bear1704 3년 전 0

luniro 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말