굳건하게

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

[ 알고리즘풀이 ]

 문제에서 원하는 조건대로 cmp 함수를 작성하여 STL sort를 이용하면 됩니다.

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

using namespace std;

bool cmp(string A, string B) {
	if (A.size() < B.size())
		return true;
	else if (A.size() > B.size())
		return false;
	else {
		int sumA = 0, sumB = 0;
		for (int i = 0; i < A.size(); i++){
			if ('0' <= A[i] && A[i] <= '9')
				sumA += A[i] - '0';
			if ('0' <= B[i] && B[i] <= '9')
				sumB += B[i] - '0';
		}
		if (sumA < sumB)
			return true;
		else if (sumA > sumB)
			return false;
		else {
			if (A < B)
				return true;
			else
				return false;
		}
		
	}
}

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

	int N;
	string input;
	vector<string> list;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		list.push_back(input);
	}
	sort(list.begin(), list.end(), cmp);
	for (int i = 0; i < N; i++)
		cout << list[i] << '\n';
	return 0;
}

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

[ 알고리즘풀이 ]

1. 백트레킹을 통해 입력된 회전 연산에 대해서 가능한 모든 순서 쌍을 정한다.

2. 순서 쌍이 정해지면 Map을 tempMap에 복제해 순서 쌍대로 tempMap에 회전 연산을 진행한다.

3. 회전 연산이 끝나면 RowSum 중에 가장 작은 값을 뽑아 답을 갱신한다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef struct turn {
	int r, c, s;
}turn;

int N, M, K, map[51][51] = {}, ans = 987654321;
turn list[6] = {};
vector<int> v;
bool visited[6] = {};

int getMinRowsum(int tempMap[51][51]) {
	int t = 987654321;
	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int j = 1; j <= M; j++)
			sum += tempMap[i][j];
		t = min(sum, t);
	}
	return t;
}

void turnOperation(int tempMap[51][51], int r, int c, int s) {
	for (int i = s; i > 0; i--) {
		int temp = tempMap[r - i][c - i];
		for (int j = -i; j < i; j++)
			tempMap[r + j][c - i] = tempMap[r + j + 1][c - i];
		for (int j = -i; j < i; j++)
			tempMap[r + i][c + j] = tempMap[r + i][c + j + 1];
		for (int j = i; j > -i; j--)
			tempMap[r + j][c + i] = tempMap[r + j - 1][c + i];
		for (int j = i; j > -i + 1; j--)
			tempMap[r - i][c + j] = tempMap[r - i][c + j - 1];
		tempMap[r - i][c - i + 1] = temp;
	}
}

void startTurn(void) {
	int tempMap[51][51] = {};
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			tempMap[i][j] = map[i][j];

	for (int i = 0; i < K; i++)
		turnOperation(tempMap, list[v[i]].r, list[v[i]].c, list[v[i]].s);
	
	ans = min(ans, getMinRowsum(tempMap));
	return;
}

void permutation(int c) {
	if (c == K) {
		startTurn();
		return;
	}
	for(int i = 0; i < K; i++)
		if (visited[i] == false) {
			visited[i] = true;
			v.push_back(i);
			permutation(c + 1);
			v.pop_back();
			visited[i] = false;
		}
	return;
}

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

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> map[i][j];

	for (int i = 0; i < K; i++)
		cin >> list[i].r >> list[i].c >> list[i].s;

	permutation(0);
	cout << ans;

	return 0;
}

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

[ 알고리즘풀이 ]

 모든 도시를 출발점으로 삼아 각각 다른 모든 도시를 탐방할 때까지 DFS 탐색을 진행합니다. 모든 도시를 탐방했다면, 답을 갱신합니다.

#include<iostream>
#include<algorithm>

using namespace std;

bool visited[10] = {};
int ans = 987654321, N, map[10][10] = {};

void DFS(int init, int s, int c, int sum) {
	if (c == N) {
		if (map[s][init])
			ans = min(ans, sum + map[s][init]);
		return;
	}
	for(int i = 0; i < N; i++)
		if (visited[i] == false && map[s][i] != 0) {
			visited[i] = true;
			DFS(init, i, c + 1, sum + map[s][i]);
			visited[i] = false;
		}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
	for (int i = 0; i < N; i++) {
		visited[i] = true;
		DFS(i, i, 1, 0);
		visited[i] = false;
	}
	cout << ans;
	return 0;
}

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

[ 알고리즘풀이 ]

1. Map에서 가능한 모든 경우에 대해(인접한 곳) 색깔을 바꾼다.

2. 색깔을 바꾼 Map에 대해서 최대 Score를 계산해 답을 갱신한다.

#include<iostream>
#include<algorithm>

using namespace std;
int N, ans = -1;
char map[50][51] = {};

int getScore(char tempMap[50][51]) {
	int m = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int score1 = 0, score2 =0;
			for (int k = j; k < N; k++)
				if (tempMap[i][j] == tempMap[i][k])
					score1++;
				else
					break;
			for (int k = i; k < N; k++)
				if (tempMap[i][j] == tempMap[k][j])
					score2++;
				else
					break;
			m = max(m, score1);
			m = max(m, score2);
		}
	}
	return m;
}

void Change(int a, int b, int c, int d) {
	char tempMap[50][51] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tempMap[i][j] = map[i][j];
	char temp = tempMap[a][b];
	tempMap[a][b] = tempMap[c][d];
	tempMap[c][d] = temp;
	ans = max(ans, getScore(tempMap));
	return;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> map[i];
	// colChange
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N - 1; j++)
			Change(i, j, i, j + 1);
	for (int j = 0; j < N; j++)
		for (int i = 0; i < N - 1; i++)
			Change(i, j, i + 1, j);
	cout << ans;
	return 0;
}