[백준/C++] 30425 Re-verse

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

 

코드

#include <iostream>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main()
{
	FASTIO;
	int n, ans=1;
	cin >> n;
	string s, tmp;
	cin >> s;
	tmp = s;

	for (int i = 1; i < n; i++) {
		if (s[i] == s[0]) {
			for (int j = i+1, idx = 1; idx < n; j++, idx++) {
				if ( j >= n) tmp += s[idx];
				else if (s[j] != s[idx]) break;
			}
			if (tmp.length() >= 2 * n - 1) break;
		}
	}

	for (int i = 1,idx, j; i < n; i++) {
		idx = 0;
		for (j = 0; idx < n; j++, idx++) {
			if (tmp[i + j] != s[idx]) break;
		}
		if (idx == n) ans++;
	}
	cout << ans;
	return 0;
}

설명

필요한 변수들을 입력받고 첫 번째 이중 for문에서는 돌림노래를 만든다. j가 n보다 크거나 같을 때는 문제에서 주어진 문자열이 끝난 것이므로 여기에서부터 직접 문자열을 더해나가면 된다. 문자열의 최대 길이는 주어진 문자열의 끝에서 시작하는 경우에 나오게 되므로 2*n-1이 된다. 따라서 문자열의 길이가 2*n-1 이상이 되면 바로 돌림노래를 만드는 것을 끝낸다.

 

두 번째 이중for문에서는 돌림노래가 가능한 횟수를 센다. 내부 for문을 break 없이 탈출했다면 돌림노래가 가능하다는 의미이므로 ans를 1씩 증가시켜준다.

느낀 점

처음에는 문제를 잘못 이해해서 틀렸다. 돌림노래가 가능하면 그 구간부터 바로 노래를 이어나가야 한다. (예를 들어 AABCAA이면  AABCAABCAABC... 이런 식으로 이어진다.) 그래서 이 부분을 이해하고 바로 코드를 짰는데, 첫 번째 이중for문 내 내부 for문에서 idx를 0으로 초기화해서 이걸 찾느라 10분 이상 소모했다...

 

처음에 잘못 이해하지 않았다면 어렵지 않은 문제인 것 같아서 아쉽다.