Kiki Devlog

[1158번][실5] 요세푸스 문제 본문

Coding Test/백준

[1158번][실5] 요세푸스 문제

kimkiki 2022. 3. 12. 19:55
728x90

수정 전 코드에서 1 1을 넣으면 마지막에 ">"이 출력되지 않는 반례가 있어서 한번 틀렸던 문제.

식을 세우는데 시간이 걸리고 코드 구현은 쉬웠던 문제임

 

내 코드

#include<iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> v;
	int totalSize;
	int range;
	int index=0;

	cin >> totalSize>> range;
	range--;

	for (int i = 1; i <= totalSize; i++) {
		v.push_back(i);
	}
	
    /*첫 원소 출력*/
	index += range;
	cout << "<"<< v[index];
	v.erase(v.begin() + index);

	/*나머지 원소 출력*/
	for (int i = 1; i < totalSize; i++) {
		index += range;
		while (index >= v.size()) {//인덱스가 vector크기를 넘어가면 차이값만큼 다시 앞에서부터 세기
			index -= v.size();
			if (index < 0)
				index = 0;
		}
		cout <<", " <<v[index];
		v.erase(v.begin()+index);
	}
	
	cout << ">";
	
	return 0;
}

 

1158번: 요세푸스 문제 (acmicpc.net)

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

 

+ 오늘 열리는 실버컵 대회가 있어서 들어가봤는데 너무 어려웠다. 코드 구현이 어려운게 아니라 식 세우는게 어려운 문제였다. 그래두 골드 위(티어 이름도 잘 모름) 사람들이 푸는 정도의 난이도인것 같아서 마음이 놓이면서도,, 그 사람들도 나랑 비슷한 또래일텐데 빨리 발전해야겠다 싶었다. 내 속도대로 파이팅! 난 실4가 눈앞임 :)

++ 알고보니 그 문제 골3문제였음 어쩐지 어렵더라. 골드돼서 혼내주러간다 딱기다려

Comments