굳건하게

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

[알고리즘풀이]

기본 아이디어는 길이 N이 될 때까지, 백트레킹을 이용해 한 자리씩 수열을 늘려간다.

이때, 좋은 수열 중 가장 작은 수를 만들어야 하므로 1부터 차례대로 수열에 추가해본다.

-수열에 숫자 추가.

좋은 수열이 되려면 수열[i] 와 수열[i+1]은 달라야 하므로 새롭게 추가되는 수는 수열의 마지막 부분과 달라야 한다.

	for (int i = 1; i <= 3; i++) {
		if (N[N.size() - 1] == i)
			continue;
		N.push_back(i);
		if (check(N))
			bt(n, N);
		N.pop_back();
	}

따라서 1 부터 3 을 넣어볼 건데, 수열 N의 마지막 자리인 N[N.size() - 1] 과 같은 수는 넣어볼 필요가 없다.

-수열이 좋은 수열인지, 나쁜 수열이 Check.

수열 N이 좋은 수열인지, 나쁜 수열인지 check 해야 한다.

check는 2개씩 (N.size() / 2) 개까지 check를 해봐야 한다.

bool check(vector<int> N) {
	int k = N.size() / 2;
	for (int i = 2; i <= k; i++) {
		for (int j = 0; j < N.size() - 2 * i + 1; j++) {
			bool flag = true;
			for (int l = 0; l < i; l++){
				if (N[j + l] != N[j + i + l]) {
					flag = false;
					break;
				}
			}
			if (flag)
				return false;
		}
	}
	return true;
}

인덱싱이 조금 까다로워서 주의해야 한다.

-최종코드

#include<iostream>
#include<vector>

using namespace std;

bool check(vector<int> N) {
	int k = N.size() / 2;
	for (int i = 2; i <= k; i++) {
		for (int j = 0; j < N.size() - 2 * i + 1; j++) {
			bool flag = true;
			for (int l = 0; l < i; l++){
				if (N[j + l] != N[j + i + l]) {
					flag = false;
					break;
				}
			}
			if (flag)
				return false;
		}
	}
	return true;
}
void bt(int n, vector<int> N) {
	if (N.size() == n) {
		for (int i = 0; i < n; i++)
			cout << N[i];
		exit(0);
	}

	for (int i = 1; i <= 3; i++) {
		if (N[N.size() - 1] == i)
			continue;
		N.push_back(i);
		if (check(N))
			bt(n, N);
		N.pop_back();
	}
}

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

	int n;
	cin >> n;
	vector<int> N;
	N.push_back(1);
	bt(n, N);
}

문제 : https://www.acmicpc.net/problem/1600

[알고리즘풀이]

우선, BFS 탐색입니다. 하지만 방문한 지점을 일반적인 2차원 배열로 check 한다면 문제를 해결할 수 없습니다.

(x, y) 지점에 말처럼 i 번 뛰어서 도착한 것과, j 번 ( i ≠ j ) 뛰어서 도착한 것은 다른 경우의 수이기 때문입니다.

따라서, (x, y) 지점에 말처럼 i 번 뛰어서 도착한 적이 있다고, j 번 뛰어서 도착한 경우를 탐색 안 하면 안 됩니다.

즉,  visited를 3차원 배열로 check 해줘야 합니다.

bool map[x][y] : (x, y) 지점이 갈 수 있는 곳인가 아닌가.

bool cmap[x][y][k] : (x, y) 지점에 k번 말처럼 뛰어서 도착한 적이 있는가.

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

queue<pair<int, int>> P, L;
int k, w, h;
bool map[200][200], cmap[200][200][30];
bool flag = true;
int h_x[8] = { -1,-2,-2,-1,1,2,2,1 };
int h_y[8] = { -2,-1,1,2,-2,-1,1,2 };
int d_x[4] = { -1, 0, 1, 0 };
int d_y[4] = { 0, -1, 0, 1 };

bool check(int x, int y) {
	if (0 <= x && x < w && 0 <= y && y < h)
		return true;
	return false;
}

void BFS() {
	P.push(make_pair(0,0));
	L.push(make_pair(0,0));

	while (!P.empty()) {
		pair<int, int> p = P.front(), l = L.front();
		P.pop(), L.pop();

		int x = p.first, y = p.second, length = l.first, horse = l.second;

		if (x == w - 1 && y == h - 1) {
			flag = false;
			cout << length;
			break;
		}

		int s_x, s_y;
		if (horse < k) {
			for (int i = 0; i < 8; i++) {
				s_x = x + h_x[i];
				s_y = y + h_y[i];
				if (check(s_x, s_y) && map[s_x][s_y] == 0 && cmap[s_x][s_y][horse + 1] != 1 ) {
					P.push(make_pair(s_x, s_y));
					L.push(make_pair(length + 1, horse + 1));
					cmap[s_x][s_y][horse + 1] = 1;
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			s_x = x + d_x[i];
			s_y = y + d_y[i];
			if (check(s_x, s_y) && map[s_x][s_y] == 0 && cmap[s_x][s_y][horse] != 1) {
				P.push(make_pair(s_x, s_y));
				L.push(make_pair(length + 1, horse));
				cmap[s_x][s_y][horse] = 1;
			}
		}
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> k >> h >> w;

	for (int i = 0; i < w; i++)
		for (int j = 0; j < h; j++)
			cin >> map[i][j];
	
	BFS();
	
	if (flag)
		cout << -1;
}

visited 배열을 3차원 배열로 만들면 금방 해결할 수 있지만, 3차원 배열로 생각하기가 어려웠다.

문제 : https://www.acmicpc.net/problem/14331

[알고리즘풀이]

i번째에 올 수 있는 알파벳은 ( i - 1 ), i , ( i + 1 ) 번 째에 있는 알파벳 중 하나다.

즉, ( i - 1), i , ( i + 1) 에 서로 다른 알파벳이 몇 개 있느냐에 따라 경우의 수가 달라진다.

각 자리별로 올 수 있는 알파벳의 경우의 수를 구하고, 모두 곱하면 답이 된다.

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

#define m 1000000007
using namespace std;

int main(void) {
	int t, n = 1;
	cin >> t;
	while (t--) {
		string in;
		cin >> in;
		vector<int> v;
		for (int i = 0; i < in.length(); i++) {
			int c = 0;
			if (i == 0) {
				if (in.length() != 1 && in[i] != in[i + 1])
					c += 2;
				else
					c++;
			}
			else if (i == in.length() - 1) {
				if (in[i] != in[i - 1])
					c += 2;
				else
					c++;
			}
			else {
				bool alphabet[26] = {};
				alphabet[in[i-1] - 'a'] = true;
				alphabet[in[i] - 'a'] = true;
				alphabet[in[i + 1] - 'a'] = true;
				for (int i = 0; i < 26; i++)
					if (alphabet[i])
						c++;
			}
			v.push_back(c);
		}
		long long ans = 1;
		for (int i = 0; i < v.size(); i++) {
			ans *= v[i];
			ans = ans % m;
		}
		cout << "Case #" << n++ << ": " << ans << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/12042

[알고리즘풀이]

i번째에 올 수 있는 알파벳은 ( i - 1 ), i , ( i + 1 ) 번 째에 있는 알파벳 중 하나다.

즉, ( i - 1), i , ( i + 1) 에 서로 다른 알파벳이 몇 개 있느냐에 따라 경우의 수가 달라진다.

각 자리별로 올 수 있는 알파벳의 경우의 수를 구하고, 모두 곱하면 답이 된다.

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

#define m 1000000007
using namespace std;

int main(void) {
	int t, n = 1;
	cin >> t;
	while (t--) {
		string in;
		cin >> in;
		vector<int> v;
		for (int i = 0; i < in.length(); i++) {
			int c = 0;
			if (i == 0) {
				if (in.length() != 1 && in[i] != in[i + 1])
					c += 2;
				else
					c++;
			}
			else if (i == in.length() - 1) {
				if (in[i] != in[i - 1])
					c += 2;
				else
					c++;
			}
			else {
				bool alphabet[26] = {};
				alphabet[in[i-1] - 'a'] = true;
				alphabet[in[i] - 'a'] = true;
				alphabet[in[i + 1] - 'a'] = true;
				for (int i = 0; i < 26; i++)
					if (alphabet[i])
						c++;
			}
			v.push_back(c);
		}
		long long ans = 1;
		for (int i = 0; i < v.size(); i++) {
			ans *= v[i];
			ans = ans % m;
		}
		cout << "Case #" << n++ << ": " << ans << '\n';
	}
}