[Baekjoon] 백준 12871번: 무한 문자열 (c++)

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

12871번: 무한 문자열

 

최소공배수를 구하는 방법으로 문제를 풀었다.

 

1. a와 b의 길이에 대한 최소공배수를 구해서,

2. A에다가 a의부분문자열을 이어준 합을 저장하고, 그 합의 길이가 최소공배수에 도달할때 까지 반복한다.

3. B에다가 b의부분문자열을 이어준 합을 저장하고, 그 합의 길이가 최소공배수에 도달할때 까지 반복한다.

4. A와 B가 같으면 1출력, 다르면 0 출력

 

ex) 

aa
aaa

 

의 경우, aaa와 aaaaa의 길이에 대한 최소공배수 = 15 ,  문자열 길이가 15가 될때까지 부분문자열 합치기 반복

A => aaa + aaa + aaa + aaa + aaa        =   aaaaaaaaaaaaaaa

B => aaaaa + aaaaa + aaaaa        =    aaaaaaaaaaaaaaa

A = B는 같으므로 1출력.

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int gcd(int a,int b){
    int c;
    while (b != 0) {
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    string a, b; // <= 50, 소문자
    string A, B;
    // abc  ==  abcabc
    // ab  !=  abcabc
    cin >> a >> b;
    
    int minX = a.length() * b.length() / gcd(a.length(),b.length());
    while(A.length() != minX){
        A += a;
    }
    while (B.length() != minX) {
        B += b;
    }
    
    if(A == B) cout << "1";
    else cout << "0";
   
}