[백준] 2661 좋은수열

백준 2661 좋은수열 문제 풀이입니다.

좋은수열

이 문제는 dfs로 풀면 간단히 풀리는 문제였습니다. 방법은 여러개가 있겠지만 전 가능한 숫자 1,2,3 순서대로 문자에 밀어 넣으면서 좋은 수열 조건을 만족하는지 확인하고 만약 그 조건을 만족하면서 N과 길이가 같다면 그건 가장 작은 숫자기 때문에 end_flag를 만들어서 프로그램을 종료시켰습니다.

소스코드는 다음과 같습니다.

Source Code:

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

int N;
string answer = "";
bool end_flag = false;

void dfs(string tmp) {
	
	for (int i = 1; i <= tmp.length() / 2; i++) {
		for (int j = 0; j <= tmp.length() - 2 * i; j++) {
			if (tmp.substr(j, i) == tmp.substr(j + i, i)) {
				return;
			}
		}
	}

	if (tmp.length() == N) {
		answer = tmp;
		end_flag = true;
		return;
	}

	for (int i = 1; 1 <= 3; i++) {
		if (end_flag) return;
		dfs(tmp + to_string(i));
	}
}

void solve() {
	
	for (int i = 1; i <= 3; i++) {
		if (end_flag) return;
		dfs(to_string(i));
	}

}

int main() {
	cin >> N;

	solve();

	cout << answer;

	system("pause");
	return 0;
}
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 열심히 포스팅 하겠습니다. 귀찮음 덜어내기…
• 곧 CS도 올라옵니다