[C++] 백준 2661번: 좋은수열

문제 링크

2661번: 좋은수열

문제 요약

1, 2, 3으로 이루어진 수열에 대해서, 인접한 길이가 같은 두 부분 수열이 같은 것이 없으면 좋은수열이라고 한다. 길이가 N인 좋은수열 중에 최솟값을 찾아야 한다.

접근 방법

최솟값을 찾아야 하기 때문에, 1 ~ 3순으로 수를 추가합니다. 뒤에서부터 길이가 1인 부분 수열 2개, 2인 부분 수열 2개, 3인 부분 수열 2개... 순으로 비교를 하고 같은 것이 없다면 재귀호출을 해줍니다. 물론 이 부분 수열 2개의 길이의 합이, 현재 수열의 길이보다 작거나 같은 동안만 비교를 해주면 됩니다.

제 경우에는 C++의 std::string 멤버함수인 substr함수를 사용해서 간단히 비교를 했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n;
string str;

void func(int cnt)
{
	if (cnt == n)
	{
		cout << str;
		exit(0);
	}

	for (int i = 1; i <= 3; i++)
	{
		str.push_back(i + '0');
		
		bool flag = false;
		for (int j = 1; j * 2 <= cnt + 1; j++)
		{
			if (str.substr(cnt - j + 1, j) == str.substr(cnt - 2 * j + 1, j))
			{
				flag = true;
				break;
			}
		}

		if (!flag)
			func(cnt + 1);
		
		str.pop_back();
	}
}

int main(void)
{
	cin >> n;
	func(0);
}