취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2661번 문제인 좋은수열이다.
문제는 아래 링크를 확인하자.

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

수열을 문자열을 이용하여 나타내고, substr 함수를 이용하여 문제의 조건을 확인해줄 수 있다.

숫자를 붙여나가는 과정을 1, 2, 3의 순서대로 붙여나간다면 사전순으로 가장 빠른 가장 긴 문자열을 알아낼 수 있다.

물론 숫자를 붙여나가다가 "나쁜 수열"을 만난다면 그 이후는 더 탐색할 필요가 없으므로 되돌아나오자.

개수가 80개로 전체를 탐색하기에는 나올 수 있는 경우의 수가 너무 많지만(3^80), "나쁜 수열"의 비중이 매우 높아 가지치기가 매우 잘 되므로 수열 자체는 빠르게 얻어낼 수 있다.

물어볼 수 있는 개수가 80개 뿐이므로, 글쓴이는 답이 될 80개의 문자열을 코드를 이용하여 뽑아내고 이를 이용하여 O(1)에 답을 하는 코드를 제출하였다.

아래는 답의 배열을 뽑아내기 위한 전처리 코드이다. 이 코드 자체는 원하는 결과를 모두 찾은 뒤 탐색을 종료하는 구현이 되어있지 않으므로 동작시간이 오래 걸린다는 점을 유의하자. 또한, 아래 코드는 출력된 값의 마지막 항 뒤에 ','가 같이 출력하고 0번째 항은 생략하고 있는 점을 유의하자.

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

bool done[81];
string ans[81];
string s = "";

void func(int current) {
	for (int k = 1; k <= 3; k++) {
		s += to_string(k);
		bool chk = 1;
		for (int i = 1; i * 2 <= current; i++) {
			if (s.substr(current - i, i) == s.substr(current - 2 * i, i)) chk = 0;
		}
		if (chk) {
			if (!done[current]) {
				done[current] = 1;
				ans[current] = s;
				if (current == 80) {
					cout << '{';
					for (int i = 1; i <= 80; i++) cout << '"' << ans[i] << "\", ";
					cout << '}';
				}
			}
			if (current!=80) func(current + 1);
		}
		s.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	func(1);
}

아래는 제출한 소스코드이다.

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

string ans[81] = { "", "1", "12", "121", "1213", "12131", "121312", "1213121", "12131231", "121312313", "1213123132", "12131231321", "121312313212", "1213123132123", "12131231321231", "121312313212312", "1213123132123121", "12131231321231213", "121312313212312131", "1213123132123121312", "12131231321231213123", "121312313212312131231", "1213123132123121312313", "12131231321231213123132", "121312313212312131231321", "1213123132123121312313212", "12131231321231213123132131", "121312313212312131231321312", "1213123132123121312313213121", "12131231321231213123132131213", "121312313212312131231321312132", "1213123132123121312313213121321", "12131231321231213123132131213212", "121312313212312131231321312132123", "1213123132123121312313213121321231", "12131231321231213123132131213212312", "121312313212312131231321312132123121", "1213123132123121312313213121321231213", "12131231321231213123132131213212312131", "121312313212312131231321312132123121312", "1213123132123121312313213121321231213123", "12131231321231213123132131213212312131231", "121312313212312131231321312132123121312313", "1213123132123121312313213121321231213123132", "12131231321231213123132131213212312131231321", "121312313212312131231321312132123121312313212", "1213123132123121312313213121321231213123132123", "12131231321231213123132131213212312131231321231", "121312313212312131231321312132123121312313212312", "1213123132123121312313213121321231213123132123121", "12131231321231213123132131213212312131231321231213", "121312313212312131231321312132123121312313212312131", "1213123132123121312313213121321231213123132123121312", "12131231321231213123132131213212312131231321231213212", "121312313212312131231321312132123121312313212312132123", "1213123132123121312313213121321231213123132123121321231", "12131231321231213123132131213212312131231321231213212313", "121312313212312131231321312132123121312313212312132123132", "1213123132123121312313213121321231213123132123121321231321", "12131231321231213123132131213212312131231321231213212313212", "121312313212312131231321312132123121312313212312132123132131", "1213123132123121312313213121321231213123132123121321231321312", "12131231321231213123132131213212312131231321231213212313213121", "121312313212312131231321312132123121312313212312132123132131213", "1213123132123121312313213121321231213123132123121321231321312132", "12131231321231213123132131213212312131231321231213212313213121321", "121312313212312131231321312132123121312313212312132123132131213212", "1213123132123121312313213121321231213123132123121321231321312132123", "12131231321231213123132131213212312131231321231213212313213121321231", "121312313212312131231321312132123121312313212312132123132131213212312", "1213123132123121312313213121321231213123132123121321231321312132123121", "12131231321231213123132131213212312131231321231213212313213121321231213", "121312313212312131231321312132123121312313212312132123132131213212312131", "1213123132123121312313213121321231213123132123121321231321312132123121312", "12131231321231213123132131213212312131231321231213212313213121321231213123", "121312313212312131231321312132123121312313212312132123132131213212312131231", "1213123132123121312313213121321231213123132123121321231321312132123121312313", "12131231321231213123132131213212312131231321231213212313213121321231213123132", "121312313212312131231321312132123121312313212312132123132131213212312131231321", "1213123132123121312313213121321231213123132123121321231321312132123121312313212", "12131231321231213123132131213212312131231321231213212313213121321231213123132123" };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	cout << ans[N];
}