취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25643번 문제인 문자열 탑 쌓기이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열들을 순서대로 쌓아야하므로, 순서가 인접한 두 문자열 사이에 길이 1 이상인 공통인 접미사-접두사 관계의 부분문자열이 있는지를 확인하는 것으로 문제를 해결할 수 있다.

그러한 부분문자열이 있는지 여부를 알아내기 위해 겹칠 수 있는 모든 위치의 가짓수에 대해 단순히 전부 시도(브루트포스)하는 코드를 작성하고 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, slen; cin >> N >> slen; N--;
	string old; cin >> old;
	while (N--) {
		bool chk = 0;
		string s; cin >> s;
		if (old == s) chk = 1;
		for (int i = 1; i < slen; i++) {
			if (old.substr(0, i) == s.substr(slen - i, i)) chk = 1;
			if (s.substr(0, i) == old.substr(slen - i, i)) chk = 1;
		}
		if (!chk) {
			cout << 0;
			return 0;
		}
		swap(old, s);
	}

	cout << 1;
}