이민희진 (백준 28064)

안녕하세요. 오늘은 이름을 연결할 거예요.

문제

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

아이디어

모든 (i,j) (i<j)에 대해서 두 이름의 쌍이 연결 가능한지만 확인하면 됩니다.
이럴때에는 모든 1≤k≤min(len(s[i]),len(s[j]))에 대해서 i의 접미사와 j의 접두사, 또는 i의 접두사와 j의 접미사가 같은지 확인하면 됩니다.

소스코드

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

bool connect(string s, string s2)
{
    int len = s.length(), len2 = s2.length(), i;

    for (i = 1; i <= min(len, len2); i++)
    {
        if (s.substr(0, i) == s2.substr(len2 - i, i)) return true;
        if (s2.substr(0, i) == s.substr(len - i, i)) return true;
    }
    return false;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, i, j, cnt = 0;
    string s[111];

    cin >> N;
    for (i = 0; i < N; i++)
        cin >> s[i];

    for (i = 0; i < N; i++)
        for (j = i + 1; j < N; j++)
            if (connect(s[i], s[j]))
                cnt++;
    cout << cnt;
}

감사합니다.