개요

백준 2661번: 좋은 수열

• 입력
  입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

• 출력
  첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

접근 방식

1. 일단 n을 받아오므로 1,2,3으로 구성된 n자리의 숫자가 필요하고, n자리 숫자를 구현했다면 해당 수열이 좋은 수열인지 아닌지를 판단해야한다.

2. int형으로 백의자리 천의 자리값이 뭔지 알려면 해당 값으로 나누고 몫,나머지로 판단 해야해서 더 간편하게 각 숫자를 char형으로 변환하여
   문자열로 저장을 하였다.

3. 수열에서 마지막에 추가한 숫자를 넣었다 뺐다해야하므로
   해당 작업에 vector<char>자료구조를 이용해
   각 숫자를 char형으로 변환해서
   push_back, pop_back 함수를 이용하여 백트래킹을 구현하였다.

4. 모든 자리에 1,2,3이 들어가므로 각 자리에 1,2,3을 넣어보고
   좋은수열인지 판단해주는 isGoodNum()함수를 통해
   나쁜 수열이면 바로 continue 키워드로 가지치기를 하면서 진행하였다.
   다음 코드가 백트래킹 함수다.

/// <summary>
/// char형으로 만든 vector에 1,2,3을 백트래킹 방식으로 추가해보며, 각 단계마다 
/// 나쁜수열로 판단되면 가지치기를 시행하여 N자리의 좋은 수열의 최소값을 출력하는 함수
/// </summary>
/// <param name="수열을 담는 char형 벡터(totNum)"></param>
/// <param name="지금 수열의 길이(length)"></param>
void MakeNum(vector<char>& totNum,int length) {

	//길이가 N이면 지금까지 담긴 수열 출력
	if (length == N) {
		for (auto iter = totNum.begin(); iter != totNum.end(); ++iter) {
			cout << *iter-'0';
		}
		//바로 탈출하기위해 didPrinted변수 true로 설정
		didPrinted = true;
		return;
	}
	for (int i = 1; i <= 3; i++) {
		//int를 char형으로 바꾼후 넣어줌
		totNum.push_back(i+'0');
		//각 totNum마다 좋은수열인지 체크후 나쁜수열이면 가지치기 시행
		if (isGoodNum(totNum, 0)) {
			MakeNum(totNum, length + 1);
			//다음스텝을 방문했다가 나쁜수열이라 돌아오면 지금 넣어준값 빼주고 진행해야함
			totNum.pop_back();
		}
		else {
			//나쁜수열일시 지금 넣어준 값 빼서 초기화해주고 continue
			totNum.pop_back();
			continue;
		}
		//출력했다면 바로 탈출하기위해 return
		if (didPrinted) return;
	}
}

5. isGoodNum함수는 총 수열과 어느 원소부터 비교할 것인지를 인자로 받는 함수이다.
   비교할 원소의 숫자를 정한 후( i ),
   해당 숫자( i )만큼 앞 수열(front)에 원소를 복사하고,
   뒷수열(back)에 그다음 원소들을 해당 숫자(i)만큼 복사해준 후 비교한다.

/// <summary>
/// N이 좋은 수열인지 판단하는 함수
/// </summary>
/// <param name="판단할 숫자 (N)"></param>
/// <param name="어디부터 판단할건지 (offset)"></param>
/// <returns>N이 좋은 수열이면 true, 나쁜 수열이면 false </returns>
bool isGoodNum(vector<char>& num,int offset) {
	//num의 사이즈를 저장
	int N = num.size();
	//num의 사이즈가 1일시 비교할게없으므로 바로 true
	if (N == 1) return true;
	//offset이 벡터의 사이즈면 true 리턴
	if (offset == N) return true;

	//i는 비교할 앞,뒤 인접수열의 사이즈
	for (int i = 1; i <= N; i++) {
		//인접수열에서 앞수열, 뒷수열
		string front = "", back = "";
		//offset부터 N까지 원소의 갯수보다 비교할 사이즈가 더커버리면 반복문 탈출
		if ((N-offset) < i*2) break;
		//offset부터 i개의 수를 앞수열에 저장
		for (int j = offset; j < offset + i; j++) {
			front += num[j];
		}
		//그다음 범위인 offset+i부터  i개의 수를 뒷수열에 저장후
		for (int j = offset + i; j < offset + 2 * i; j++) {
			back += num[j];
		}
		//string헤더의 compare함수로 비교 둘이 같다면 나쁜수열이므로 false리턴
		if (!front.compare(back)) return false;
	}
	//다음 offset부터 또 비교를 해나가서 나쁜 수열이나오면 false 리턴
	if (!isGoodNum(num, offset + 1)) return false;
	//반복문빠져나오면 true
	return true;
}

코드

#include<iostream>
#include<vector>
//for string.compare()
#include<string>

using namespace std;
int N=0;
vector<char> num;
bool didPrinted = false;

void Input() {
	cin >> N;
}

/// <summary>
/// N이 좋은 수열인지 판단하는 함수
/// </summary>
/// <param name="판단할 숫자 (N)"></param>
/// <param name="어디부터 판단할건지 (offset)"></param>
/// <returns>N이 좋은 수열이면 true, 나쁜 수열이면 false </returns>
bool isGoodNum(vector<char>& num,int offset) {
	//num의 사이즈를 저장
	int N = num.size();
	//num의 사이즈가 1일시 비교할게없으므로 바로 true
	if (N == 1) return true;
	//offset이 벡터의 사이즈면 true 리턴
	if (offset == N) return true;

	//i는 비교할 앞,뒤 인접수열의 사이즈
	for (int i = 1; i <= N; i++) {
		//인접수열에서 앞수열, 뒷수열
		string front = "", back = "";
		//비교할 원소의 갯수보다 비교할 사이즈가 더커버리면 반복문 탈출
		if ((N-offset) < i*2) break;
		//offset부터 i개의 수를 앞수열에 저장
		for (int j = offset; j < offset + i; j++) {
			front += num[j];
		}
		//그다음 범위인 offset+i부터  i개의 수를 뒷수열에 저장후
		for (int j = offset + i; j < offset + 2 * i; j++) {
			back += num[j];
		}
		//string헤더의 compare함수로 비교 둘이 같다면 나쁜수열이므로 false리턴
		if (!front.compare(back)) return false;
	}
	//다음 offset부터 또 비교를 해나가서 나쁜 수열이나오면 false 리턴
	if (!isGoodNum(num, offset + 1)) return false;
	//반복문빠져나오면 true
	return true;
}

/// <summary>
/// char형으로 만든 vector에 1,2,3을 백트래킹 방식으로 추가해보며, 각 단계마다 
/// 나쁜수열로 판단되면 가지치기를 시행하여 N자리의 좋은 수열의 최소값을 출력하는 함수
/// </summary>
/// <param name="수열을 담는 char형 벡터(totNum)"></param>
/// <param name="지금 수열의 길이(length)"></param>
void MakeNum(vector<char>& totNum,int length) {

	//길이가 N이면 지금까지 담긴 수열 출력
	if (length == N) {
		for (auto iter = totNum.begin(); iter != totNum.end(); ++iter) {
			cout << *iter-'0';
		}
		//바로 탈출하기위해 didPrinted변수 true로 설정
		didPrinted = true;
		return;
	}
	for (int i = 1; i <= 3; i++) {
		//int를 char형으로 바꾼후 넣어줌
		totNum.push_back(i+'0');
		//각 totNum마다 좋은수열인지 체크후 나쁜수열이면 가지치기 시행
		if (isGoodNum(totNum, 0)) {
			MakeNum(totNum, length + 1);
			//다음스텝을 방문했다가 나쁜수열이라 돌아오면 지금 넣어준값 빼주고 진행해야함
			totNum.pop_back();
		}
		else {
			//나쁜수열일시 지금 넣어준 값 빼서 초기화해주고 continue
			totNum.pop_back();
			continue;
		}
		//출력했다면 바로 탈출하기위해 return
		if (didPrinted) return;
	}
}

void Solution() {
	MakeNum(num, 0);

}

int main() {
	Input();
	Solution();
}

문풀후생

처음엔 백트래킹 함수에서 각 단계마다 좋은 수열인지 비교하지 않았다.
수열이 N개의 사이즈가 될때 좋은 수열인지 판단하는 식으로
구현했더니 N이 10만 되어도 3^10개의 수열이 나오고 해당 수열을 전부
판단하려하니 시간이 초과가 되었다.

이 시간초과를 해결하러 여기저기 검색해본 결과 가지치기 얘기를 보고
딱 방법이 떠올랐다.

훌륭한 가지치기!