[백준 2661] 좋은 수열

문제링크 : https://www.acmicpc.net/problem/2661

💻 문제 풀이 : C++

🤣1st Try...

#include <iostream>
#include <vector>
#include <string>

#define MAX_DEPTH 85

using namespace std;

int N;
// vector<int> selected;
// vector<int> v_ans;
string selected;
string s_ans;


// int isLess(vector<int> a, vector<int> b)
int isLess(string a, string b)
{
	// int size = a.size();
	// if (size != b.size()) return 0;

	for (int i = 0; i < N ; i++)
	{
		if (a[i] < b[i]) return 1;
		else if (a[i] > b[i]) return 0;
	}
	return 0;
}

void dfs(int depth, int n)
{
	if (depth == n)
	{
		/* 좋은 수열 판단 */
		for (int i = 1; i <= n / 2; i++)
		{
			for (int j = 0; j <= n-i ; j++)
			{
				string a = selected.substr(j, i);
				string b = selected.substr(j+i, i);
				if (!a.compare(b)) return;
				int debug = 1;
			}
		}

		///* debug */
		//for (int i = 0; i < depth; i++)
		//	cout << selected[i] << " ";
		//cout << endl;
		
		// 최소 판단
		if (!isLess(s_ans, selected))
			s_ans = selected;
		return;
	}

	for (int i = '1'; i <= '3'; i++)
	{
		selected.push_back(i);
		dfs(depth + 1, n);
		selected.pop_back();
	}
}

int main()
{
	cin >> N;

	for (int i = 0; i < 40; i++)
		s_ans.push_back('9');

	// N자리 수 만들기
	dfs(0, N);

	for (int i = 0; i < N ; i++)
		cout << s_ans[i];
	cout << endl;


	return 0;
}

=> Backtracking을 하지 않아 시간초과!!

2nd Try

#include <iostream>
#include <vector>
#include <string>

#define MAX_DEPTH 85

using namespace std;

int endFlag = 0;
int N;
string selected;

void dfs(int depth, int n)
{
	if (endFlag == 1)
		return;

	int len = selected.length();
	for (int i = 1; i <= len / 2; i++)
	{
		string a = selected.substr(len - i, i);
		string b = selected.substr(len - i * 2, i);
		if (!a.compare(b)) return;
	}

	if (depth == n)
	{
		cout << selected << endl;
		endFlag = 1;
		return;
	}

	for (int i = '1'; i <= '3'; i++)
	{
		selected.push_back(i);
		dfs(depth + 1, n);
		selected.pop_back();
	}
}

int main()
{
	cin >> N;

	// N자리 수 만들기
	dfs(0, N);

	return 0;
}

=> 작은숫자부터 넣으므로, 조건에 부합하는 첫번째 수가 정답!!
⭐ 가지치기
1. Flag로 계속 return하기
2. 조건에 다 맞으면 check하는게 아니라
=> 매 재귀마다 check해서 조건을 끝까지 확인하지 않아도 되도록

다른 풀이법

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

int N;
string result;
bool finish = false;

void solve(string tmp,int cnt) {
	if (finish ) return;
	int size = tmp.size();
	for (int i = 1; i <= size / 2; i++) {//규칙검사
		if (tmp.substr(size - i, i) == tmp.substr(size - 2 * i, i)) return;
	}
	if (cnt == N) {
		result = tmp;
		finish = true;
	}
	for (int i = 0; i < N; i++) {//백트래킹
		solve(tmp + "1", cnt + 1);
		solve(tmp + "2", cnt + 1);
		solve(tmp + "3", cnt + 1);
	}
}

int main() {
	cin >> N;
	solve("",0);
	cout << result << endl;
}

💻 문제 풀이 : Python

import sys

n = int(input())
s = []

def dfs(depth):
    for i in range(1, (depth//2 + 1)):
        if s[-i:] == s[-2*i:-i]: return -1

    if depth == n:
        for i in range(n): print(s[i], end='')
        return 0

    for i in range(1, 4):
        s.append(i)
        if dfs(depth + 1) == 0: return 0
        s.pop()

dfs(0)

---

📌 memo

😊 C++

string 활용하기

1. int의 자리수가 큰 경우 string을 활용해서 후연산 진행!!
2. substr(start_point, how_long_substr)

#include <string>

	string a = selected.substr(j, i);
	string b = selected.substr(j+i, i);

😊 Python

list 자르기

if s[-i:] == s[-2*i:-i]: return False

---

ref)
👍코드의 신인가...
https://minocode.tistory.com/14
다른 풀이 참고
https://lu-coding.tistory.com/74