[백준] 2661-좋은수열(C++)

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

2661번: 좋은수열

 

정답률에 비해서 어려운 문제였습니다.

우선, 규칙성이 있는지 확인하셔야 합니다. 하지만 수가 늘어남에 따라 규칙성이 변화하는 형태로 별다른 규칙이 없었습니다. 그렇다면 완전탐색을 고려해보아야 합니다. 마침 n도 1 이상 80이하로 비교적 적은 수 입니다. 단순히 모든 수를 넣어보고 비교한다면 시간초과가 날 것입니다. 백트래킹에 대한 개념을 아셔야 합니다.

 

 

백트래킹이란?

주로 dfs에서 사용되는 개념입니다. 가지치기라고 생각하면 됩니다. 완전탐색시에 모든 경우의 수 를 고려해서 결과를 도출합니다. 하지만 완탐은 시간이 어마어마하게 들어가는 비효율적인 방법입니다. 

백트래킹은 완전탐색시에 가능성이 있는 경우의 수들만 추려내면서 탐색을 하는 방법입니다.  

 

이번 문제는 직접 코드를 보시는게 이해가 빠릅니다. 

#include <iostream>
#include <string>
using namespace std;
int n = 0;
bool ended = 0;
bool isValid(string val) {
	
	int len = val.size();
	int ended = val.size() - 1;

	for (int i = 1; i <= len / 2; i++) {
		string first = val.substr(ended - i, i);
		string second = val.substr(ended, i);
		if (first.compare(second) == 0) return false;
		ended--;
		
	}
	return true;
}

void dfs(int cnt, string val) {
	if (ended == 1)
		return;
	if (!isValid(val))  return;
	if (cnt == n) {
		cout << val <<"\n";
		ended = 1;
		return;
	}

	dfs(cnt + 1, val + '1');

	dfs(cnt + 1, val + '2');

	dfs(cnt + 1, val + '3');

}
int main() {
	cin >> n;
	dfs(0, "");
}

 

dfs 함수입니다.

void dfs(int cnt, string val) {
	if (ended == 1)
		return;
	if (!isValid(val))  return;
	if (cnt == n) {
		cout << val <<"\n";
		ended = 1;
		return;
	}

	dfs(cnt + 1, val + '1');

	dfs(cnt + 1, val + '2');

	dfs(cnt + 1, val + '3');

}

보시는 것 처럼 전형적인 dfs 재귀 함수입니다. 

종료되는 시점은 cnt == n 일때 입니다. ( 1부터 2, 3번 순서로 탐색하기에 가장먼저 도착한 친구가 가장 값이 작습니다.)

하지만 추가된 ended == 1, isValid()  2조건이 포함되기때문에 백트래킹입니다.  ended는 출력초과를 막기위해 당연히 필요한 함수입니다. (겸사겸사 가지치기도 하게됩니다.)

그리고 isValid 함수를 통해서  해당 문자열이 유효한지 확인하고 유효할 경우에만 더 진행되는 구조입니다.

전형적인 백트래킹 문제였지만, 구현난이도가 낮지 않아서 저도 valid 함수에서 막혔던 문제입니다.

 

 

안보고 코드를 직접 입력하면서 꼭 손으로 풀어보세요!