[CodeForces] 코드포스 Typical Interview problem 문제풀이(C++)

FB-String이 "FBFFBFFB"가 무한반복 된다는 것을 떠올리면 됨

 -> 크게 어렵진 않지만, 이유를 아는 것이 중요

 

* 1부터 시작해서 숫자를 올리며 추가하다 보면, 3과 5의 최소공배수인 15인 경우가 발생하는데, 이 이후부터는 패턴이 반복되므로 위 문자열 무한반복

 

처음 숫자 : 1 -> 아무것도 안함

숫자 : 2 -> 아무것도 안함

숫자 : 3 -> "F" 추가

숫자 : 4 -> 아무것도 안함

숫자 : 5 -> "B" 추가 -> "FB"

숫자 : 6 ->  "F" 추가 -> "FBF"
숫자 : 7, 8 -> 아무것도 안함

숫자 : 9 -> "F"추가 -> "FBFF"

숫자 : 10 -> "B"추가 -> "FBFFB"

숫자 : 11 -> 아무것도 안함

숫자 : 12 -> "F"추가 -> "FBFFBF"

숫자 : 15 -> "F", "B"추가 -> "FBFFBFFB"

 

16 이후부터는 위의 과정 반복 -> "FBFFBFFB" 반복

#include<iostream>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
 
/*
<문제> 2초, 512메가
FB-string 처음엔 비어있고, 양수로 채움
1부터 오름차순으로
3으로 나누어떨어지면 F을 FB-string에 추가
5로 나누어 떨어지면, B를 FB-string에 추가
둘 다 나누어떨어지면 "FB"를 추가 
 
F/B로 이루어진 문자열을 받았을 때, 
이것이 FB-string인지를 판별
즉, 이 문자열이 l~r까지의 FB-string인지룰 판별
 
<입력>
t    테스트케이스(~2046)
각 테스트케이스마다 두 줄
k     FB-문자열 수(<=10)
s    FB-문자열
 
<출력>
YES 또는 NO(각 테스트케이스마다)
 
<풀이>
이게 FBFFBFFB가 계속 반복됨
즉, 주어진 문자열 1~10개를 위 문자열 세 번 나열한 것에서 찾아보면 됨
-> KMP가면 되겠지만, 라이브러리 이용
 
*/
 
int main() {
    int t; cin >> t;
    string origin = "FBFFBFFBFBFFBFFBFBFFBFFB";
 
    while (t--) {    //testcase
        int k; string s; cin >> k >> s;    //문자열 수, 문자열
        if (origin.find(s) == -1) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}