글 읽기 - 시간초과 문제입니다,,

tghmjj 3년 전 0

항상 감사합니다.

시간 초과가 뜨는데 더 빠르게 할수있는 방법이 있을까요?

#include <iostream>
using namespace std;
#include <algorithm>
#include <string>

bool checkM(string before) {
	string after = before;
	reverse(after.begin(), after.end());

	for (int i = 0; i < (after.length() / 2) + 1; i++) {
		switch (before[i])
		{
		case '3':
		case '4':
		case '6':
		case '7':
		case '9':
			return false;
		default:
			break;
		}
		if (before[i] == '0' && after[i] != '0') return false;
		if (before[i] == '1' && after[i] != '1')  return false;
		if (before[i] == '2' && after[i] != '5')  return false;
		if (before[i] == '5' && after[i] != '2') return false;
		if (before[i] == '8' && after[i] != '8') return false;
	}

	return true;
}

int main() {
	long long start, end;
	long long count = 0;

	cin >> start >> end;

	for (long long i = start; i <= end; i++) {
		if (checkM(to_string(i)))
			count++;
	}

	cout << count;
    return 0;
}

39dll 3년 전 1

A = 0, B = 10^18일 때 위 코드처럼

0~10^18의 모든 숫자가 다 만족하는지 확인하면 연산 횟수가 10^18이 되어 시간 초과가 납니다.

만족하는 숫자들의 패턴을 찾아서 푸셔야 할 것 같습니다.

tghmjj 3년 전 0

감사합니다.

경우의 수를 계산하도록 해서 해결했습니다.

wie0213 9달 전 0

백트래킹으로 팰린드룸 만드는 방식으로 deque에 append하면서 순회해도 풀리긴 해요

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

문제

문제

출처

ICPC

시간초과 문제입니다,,

tghmjj 3년 전 0

39dll 3년 전 1

tghmjj 3년 전 0

wie0213 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말