(C++) - 백준(BOJ) 12871 : 무한 문자열

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

12871번: 무한 문자열

최대공약수 최소공배수를 구해 구현하는 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

s, t, ss, tt, 최소 공배수 lcmVal을 선언 후 문자열 s, t에입력받습니다.

📔 풀이과정

최소공배수만큼 문자열을 붙였을 때 둘이 같다면 무한대로 문자열을 늘려도 같습니다.

* 단순히 s.size() * t.size()만큼 문자열을 붙인다면 메모리초과를 받게 됩니다.

LCM(최소공배수) = 정수 a * 정수 b / GCD(최대공약수)(a, b)입니다. 해당 값을 함수를 수행해 구해줍니다.

반환값은 lcmVal에 저장해줍니다.

lcmVal / s.size()만큼 ss에 s문자열을 붙여줍니다.

lcmVal / t.size()만큼 tt에 t문자열을 붙여줍니다.

📔 정답출력

ss와 tt가 같은지 여부를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
string s, t, ss, tt;
int lcmVal;

int GCD(int a, int b){
    if(!b) return a;
    return GCD(b, a%b);
}

int LCM(int a, int b){
    return a*b/GCD(a,b);
}

int main(){
    cin >> s >> t;
    lcmVal = LCM(s.size(), t.size());
    for(int i = 0; i < lcmVal / s.size(); i++) ss += s;
    for(int i = 0; i < lcmVal / t.size(); i++) tt += t;
    cout << (ss == tt);
}

---

📕 Test Case

반례를 직접 작성해 보았습니다. 

input

aaa

aa

답

1