백준 2661 - 좋은 수열

문제 설명

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 좋은 수열중 가장 작은 수를 출력하면 된다.

좋은 수열이란 연속된 부분 수열 중 반복되는 부분이 없는 것을 말한다.

 

해당 문제는 dp를 이용하면 간단하게 풀 수 있다.

i개의 길이의 수열 중 1, 2, 3을 마지막으로 추가한 수열 중 가장 작은 수열을 기록하면 된다.

즉, i-1 길이의 수열에서 1, 2, 3을 추가해 보며 좋은 수열인지 확인하면 된다.

 

좋은 수열인지 확인하는 방법은 1~N/2 길이만큼 두 번 잘라 끝에서부터 확인해 보면 된다.

두 번 자르는 것은 연속된 반복만 없으면 되기 때문에 마지막 숫자를 추가한 후 연속적으로 반복이 일어나는 지만 확인하면 되기 때문이다.

bool Check(string& prev)
{
	int size = prev.length();

	for (int i = 1; i <= prev.length() / 2; i++)
	{
		auto left = prev.substr(size - i * 2, i);
		auto right = prev.substr(size - i, i);

		if (left == right) return false;
	}

	return true;
}

 

해당 문제는 가장 작은 수열을 골라야 하기 때문에 숫자 비교가 필요하다.

하지만 이걸 정수 자료형으로 표현하기에는 80자리를 표현해야 하기 때문에 범위를 초과하여 string으로 관리해야 한다.

string의 대소 관계를 비교할 함수를 만들어 두면 편할 것이다.

bool IsLess(string& origin, string& target)
{
	if (origin.length() == 0) return true;

	for(int i = 0 ; i < origin.length(); i++)
	{
		if (origin[i] - '0' == target[i] - '0') continue;
		return origin[i] - '0' > target[i] - '0';
	}
}

 

이제 i-1번째 길이 에 1, 2, 3을 추가해 보며 가장 작은 좋을 수열을 고르면 된다.

dp[1][1] = "1";
dp[1][2] = "2";
dp[1][3] = "3";

for (int i = 2; i <= N; i++)
{
    for (int j = 1; j <= 3; j++)
    {
        for (int k = 1; k <= 3; k++)
        {
            if (j == k) continue;
            if (dp[i - 1][k] == "") continue;

            auto prev = dp[i - 1][k];
            prev += to_string(j);

            if (Check(prev) && (dp[i][j] == "" || IsLess(dp[i][j], prev)))
            {
                dp[i][j] = prev;
            }
        }
    }
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
vector<vector<string>> dp;

bool Check(string& prev)
{
	int size = prev.length();

	for (int i = 1; i <= prev.length() / 2; i++)
	{
		auto left = prev.substr(size - i * 2, i);
		auto right = prev.substr(size - i, i);

		if (left == right) return false;
	}

	return true;
}

bool IsLess(string& origin, string& target)
{
	if (origin.length() == 0) return true;

	for(int i = 0 ; i < origin.length(); i++)
	{
		if (origin[i] - '0' == target[i] - '0') continue;
		return origin[i] - '0' > target[i] - '0';
	}
}

int main() 
{
    INPUT_OPTIMIZE;

	cin >> N;
	dp.resize(N + 1, vector<string>(4));

	dp[1][1] = "1";
	dp[1][2] = "2";
	dp[1][3] = "3";

	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			for (int k = 1; k <= 3; k++)
			{
				if (j == k) continue;
				if (dp[i - 1][k] == "") continue;

				auto prev = dp[i - 1][k];
				prev += to_string(j);

				if (Check(prev) && (dp[i][j] == "" || IsLess(dp[i][j], prev)))
				{
					dp[i][j] = prev;
				}
			}
		}
	}


	string ans = dp[N][1];
	if (dp[N][2] != "" && IsLess(ans, dp[N][2]))
	{
		ans = dp[N][2];
	}

	if (dp[N][3] != "" && IsLess(ans, dp[N][3]))
	{
		ans = dp[N][3];
	}

	cout << ans;

	return 0;
}

---