[cpp 알고리즘] 백준 15721 번데기

[백준] 15721 번데기

알고리즘: 구현, 브루트포스 알고리즘, 시뮬레이션

https://www.acmicpc.net/problem/15721

문제 요약

- n-1회차 문장일 때는 "뻔 – 데기 – 뻔 – 데기 – 뻔(x n번) – 데기(x n번)" 로 번데기 게임이 진행된다.

- 원으로 앉아있고, 반시계방향으로 게임을 진행한다.

- T번재 '뻔' 또는 '데기'를 외치는 사람이 몇 번째 사람인지 구하는 문제이다. 

풀이 정리

구하고자 하는 T번째가 10000보다 작기 때문에, 브루트포스 알고리즘을 선택했다. 

- N=1일 때, 뻔-데기-뻔-데기-뻔-뻔-데기-데기

- N=2일 때, 뻔-데기-뻔-데기-뻔-뻔-뻔-데기-데기-데기

- N=3일 때, 뻔-데기-뻔-데기-뻔-뻔-뻔-뻔-데기-데기-데기-데기

위와 같이 진행이 되고, T번째는 N이 1000이전에 충분히 10000이 될 것이다. (넉넉하게 1000으로 잡았다.)

 

string s에 반복하면서 붙여줬고, 뻔(0)/데기(1) 중에 T번째를 구하고, 몇 번째 사람 차례인지를 알기 위해 %사람(A)를 해주었다.

C++ 코드

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

int arr[2001];
int A, T, flag;
string s;

int main(){
    
    cin >> A >> T >> flag;
    
    for(int i=0; i<=1000; i++){
        s += "0101";
        
        string news="";
        for(int j=0; j<=i+1; j++){
            news+="0";
        }
        s += news;
        
        news="";
        for(int j=0; j<=i+1; j++){
            news+="1";
        }
        s += news;
    }
    
    //T번째 flag구하기
    int cnt = 0;
    int tempidx = -1;
    if(flag == 0){
        for(int i=0; i<s.size(); i++){
            if(s[i] == '0'){
                cnt++;
                if(cnt == T){
                    tempidx = i;
                    break;
                }
            }
        }
    }
    else if(flag == 1){
        for(int i=0; i<s.size(); i++){
            if(s[i] == '1'){
                cnt++;
                if(cnt == T){
                    tempidx = i;
                    break;
                }
            }
        }
    }
    
    cout << tempidx%A;
    
    return 0;
}