배열을 활용한 /C++/조세 퍼스 / 공주구하기 / 알고리즘/

 

 

 

 

 

이번에 푼 문제는 

 

알고르짐 문제에서 조금은 유명 한 문제 조세퍼스

 

관련 문제 입니다.

 

 

우선 문제에 대해서 설명을 하자면

 

첫번째 입력 되는 값 만큼 숫자가 

 

차례대로 생기게 됩니다.

 

2번째 입력된 숫자는

 

2번째 입력한 숫자를

 

부른 사람이 아웃 

 

되는 형식으로

 

아웃된 사람 다음 사람부터

 

다시 1부터 시작하여

 

입력 받은 값을 부르게 

 

되는 사람이 아웃 되는 형식 입니다.

 

 

소스코드 맨아래

 

CPP파일을 첨부 하였습니다.

 

필요 하신분들은 다운받아

가세요.

 

---

 

 

#include <stdio.h>

#include <iostream>



using namespace std;





병사의 수만큼 1부터 입력 받은 값만큼 배열에 집어 넣습니다.



void setting(int array[], int &people , int &num) 

{

 cout << "병사의 수" << endl;

 cin >> people;



 cout << "부를수" << endl;

 cin >> num;



 for (int i = 0; i < people; i++)

 {

 array[i] = i + 1;

 }

}





배열은  Main함수에서-1로 초기화 해주었고 



삭제 해야할 숫자를 발견 하면 0을 대입하고  마지막 남은 숫자를 찾을때,

찾기 쉽게 하기 위해서 입니다.





cnt 는 1부터 시작한다 그, 이유인즉 자기자신을

포함해야 하기 때문이다.



이것이 핵심일수도 있을거 같다.









int main() 

{

 int array[10000] = { -1, }; 

 int people = 0;

 int num;

 int cnt = 1;

 int king = 0;

 int stop = 0;

 setting(array, people, num);





 while (true) 

 {



 for (int i = 0; i < people; i++) 

 {



 if (array[i] > 0)

 {

 cnt++;

 king++;

 }



 if (cnt-1 == num) 

 {

 array[i] = 0;

 cnt = 1;

 }



 if (i == people - 1 && king == 1) 

 {

 stop = king;

 break;

 }



 if (i == people - 1) 

 {

 king = 0;

 break;

 }

 }



 if (stop == 1)

 {

 break;

 }

 }





 for (int i = 0; i < people; i++) {



 if (array[i] > 0) {

 cout << array[i] << endl;

 }

 }





 //system("pause");

 return 0;

}

 

 

아래는 공주 구하기  소스 파일 입니다.

 

공주구하기_1.cpp

다운로드