글 읽기 - 당연히 시간초과가 날거라고 생각했는데 52ms로 맞았어요

hek0628 4년 전 0

for 문으로 10000까지 돌면서 셀프넘버를 벡터에 저장하고

또 for 1부터 10000까지 문을 돌면서 그 안에서 또 벡터의 사이즈 만큼을 for 문을 돌렸거든요

정말 비효율적이고 실제로 돌려봐도 30초는 넘게 걸리는데 왜 백준에서는 52ms라고 채점하는 걸까요

물론 채점 서버와 제 컴퓨터는 성능이 다르겠지만요

이렇게 푸는게 맞는건가요? 아니면 제가 비효율적으로 푼거 맞나요? 알려주시면 정말 감사하겠습니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	vector<int> v;
	for (int i = 1; i < 10000; i++) {
		if (i < 10) {
			v.push_back(i + i);
		}
		else if (i < 100) {
			v.push_back(i + i / 10 + i % 10);
		}
		else if (i < 1000) {
			v.push_back(i + i / 100 + i / 10 % 10 + i % 10);
		}
		else {
			v.push_back(i + i / 1000 + i / 100 % 10 + i / 10 % 10 + i % 10);
		}
	}
	for (int i = 1; i <= 10000; i++) {
		bool flag = false;
		for (int j = 0; j < v.size(); j++) {
			if (v[j] == i) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << i << endl;
		}
	}
	return 0;
}

djm03178 4년 전 0

Debug 모드 대신 Release 모드로 컴파일 해보세요.

코드를 봐도 그렇게 오래 걸릴 코드는 아닙니다.

hek0628 4년 전 0

답변해주셔서 감사합니다.

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

문제

문제

출처

ICPC

당연히 시간초과가 날거라고 생각했는데 52ms로 맞았어요

hek0628 4년 전 0

djm03178 4년 전 0

hek0628 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말