글 읽기 - 요세푸스 시간초과

fbrjsah0725 1년 전 0

출력은 똑같이 나오는데, 시간 초과가 뜨네요.. 어느 부분에서 바꿔야할지 잘 모르겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int a, b, count = -1, cuts;
	vector<int> v;
	cin >> a >> b;
	for (int i = 1; i <= a; i++) {
		v.push_back(i);
	}
	cuts = a;
	cout << '<';
	while (v.size() != 1) {
		for (int i = 0; (count + b) <= cuts - 1; i++) {
			count += b;
			cout << v[count - i] << ',' << ' ';
			v.erase(v.begin() + count - i);
		}
		count -= cuts;
		cuts = v.size();
	}
	cout << v.front() << '>';

}

invrtd_h 1년 전 2

std::vector의 시간복잡도를 공부하세요. 끝부분이 아닌 위치의 원소를 지우는 것은 O(지우는 원소 오른쪽 원소의 개수) = O(N)입니다. 그리고 std::queue 사용법을 알아보세요.

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

문제

문제

출처

ICPC

요세푸스 시간초과

fbrjsah0725 1년 전 0

invrtd_h 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말