SWEA 무한 문자열 - 15758(c++)

[D3] 무한 문자열 - 15758

문제 링크

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        string st;
        string stt;
        cin >> st;
        cin >> stt;
        
        if(st.length() != stt.length())
        {
            int a = st.length();
            int b = stt.length();
            int num = 1;	// 최소공배수
            int i = 2;
            while ( (a != i && b != i) && ( a != 1 && b != 1))
            {
                if (a % i != 0 || b% i != 0)
                    i++;
                else
                {
                    num *= i;
                    a /= i;
                    b /= i;
                    i=2;
                }
            }
            num = num * a * b;
            a = st.length();
            b = stt.length();
            i = 0;
            while (st.length() != num)
            {
                st += st[i % a];
                i++;
            }
             i = 0;
            while (stt.length() != num)
            {
                stt += stt[i % b];
                i++;
            }
        }
        if(st == stt)
            cout << "#" << test_case << " " << "yes" << "\n";
        else
            cout << "#" << test_case << " " << "no" << "\n";
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

처음 이문제를 풀 때 문자열의 길이가 더 짧은쪽의 길이를 긴쪽의 길이만큼 자신을 반복해서 늘려주면 해결할 수 있을 것이라 봤지만 실패했다

그래서 두 문자열 모두 늘려주어야겠다고 생각했고 두 문자열의 길이의 최소공배수만큼 늘려주면 무한대까지 늘렸을 때와 결과가 같다는 것을 알게 되었고 최소 공배수만큼 문자를 늘려주었다.