브루트포스_연습

1. 리모컨

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

1107번: 리모컨

숫자를 누르는 순간 지금까지 눌렀던 +,- 는 의미 없어짐.
중복이 있는 경우는 절대 최소가 될 수 없다.

숫자 다음에 +,-가 결정되야함
+와 - 중 하나만 써야함

이동할 채널 C를 정한다(0~100만)
C에 고장난 숫자가 있는지 결정(수를 하나씩 체크), 가능하면 몇번 누르는지 횟수 반환하기
두 채널의 차이만큼 횟수 계산 가능

초기값에서 이동하는 경우도 체크(예외처리)

 

풀이

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

vector<bool> num(10, true);
int check(int);

int main() {
	int n, m, min = 500000;
	cin >> n >> m;

	// 입력받기
	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		num[temp] = false; // 불가능
	}

	// 번호누르기
	for (int i = 0; i <= 1000000; i++) {
		// 가능하다면
		int cnt = check(i);
		int temp_ans;
		if (cnt) {
			// 몇번이동해야 하는지 체크
			temp_ans = cnt + abs(n - i);

			// 더 작으면 min 갱신
			if (min > temp_ans)
				min = temp_ans;
		}
	 }

	// 예외처리(번호 안누를 수 있으면)
	if (abs(n - 100)< min)
		min = abs(n - 100);

	cout << min << endl;

}

// 고장난 버튼이 있는지 체크
int check(int number) {
	char temp[100];
	sprintf(temp, "%d", number);

	for (int i = 0; i < strlen(temp); i++) {
		if (!num[temp[i] - '0'])
			return false;
	}
	return strlen(temp);
}

2. 카잉달력

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

6064번: 카잉 달력

몇 번째 해 인지 구하기.
M으로 나눈 나머지가 x인 모든 해만 구해보기 i×M+x (i ≥ 0)

즉 모든 해를 찾을 필요 없이 나머지에 맞춰서 M만큼 증가하면서 탐색하면 된다.

단, 0년 째를 찾기 위해 입력 받은 x와 y를 -1 씩 해줘야 한다.

풀이

#include <iostream>
using namespace std;

int main() {
	int total;
	cin >> total;

	for (int cnt = 0; cnt < total; cnt++) {
		// 입력받기
		int m, n, x, y;
		cin >> m >> n >> x >> y;
		x -= 1, y -= 1;

		int sc = x;

		// 반복처리
		while (true) {
			// 찾았으면
			if (sc % n == y)
				break;
			
			// 없으면
			if (sc > m*n) {
				sc = -2;
				break;
			}
			sc += m; // 더하기
		}

		// 출력
		cout << sc+1 << endl;
	}
}

 

3. 수 이어쓰기

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

1748번: 수 이어 쓰기 1

수의 길이를 활용하기
1~9 = 1, 10~99 = 2, 100~999 = 3, 이런식으로 수의 길이를 계산해서 더해준다!

 

풀이

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

int main() {
	int n, cnt=0, ans=0;
	cin >> n;

	// 자리수 cnt
	int temp = n;
	while (temp) {
		cnt += 1;
		temp /= 10;
	}

	// 자리수 동안 더하기
	for (int i = 1; i < cnt; i++) {
		// 이전 자리수 개수 구하기
		int val = (int)pow(10.0, (double)i) - (int)pow(10.0, (double)i - 1);
		ans += val*i;
	}

	// 마지막 자리수 더하기
	int val = n - (int)pow(10.0, (double)cnt - 1) +1; // 본인 자리까지 더하기
	ans += val*cnt;

	// 출력
	cout << ans;
}

4. 부등호

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

2529번: 부등호

풀이의 핵심은 순열을 사용한다.

순열은 차례로 값이 커지므로 가장 큰 값을 구할때는 가장 큰 값을 가지고와서 이전 순열로 내려가면서 체크하고

가장 작은 값을 구할 때는 가장 작은 값을 가지고와서 다음 순열로 올라가면서 체크한다

 

풀이

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

bool check(vector<int> & d, vector<char> &a);
int main() {
	int n, min = 0, max = 0;
	cin >> n;

	// 입력처리
	vector<char> a(n);
	vector<int> d(n+1);
	vector<int> d2(n + 1);

	for (int i = 0; i < n; i++) 
		cin >> a[i];

	// 작은 수, 큰수
	for (int i = 0; i <= n; i++) {
		d[i] = i;
		d2[i] = 9 - i;
	}

	do {
		// 가능하면 체크
		if (check(d, a)) {
			break;
		}
		// 안되면 종료
	} while (next_permutation(d.begin(), d.end()));

	do {
		// 가능하면 체크
		if (check(d2, a)) {
			break;
		}
		// 안되면 종료
	} while (prev_permutation(d2.begin(), d2.end()));

	for (int i = 0; i < d2.size();i++) {
		cout << d2[i];
	}
	cout << endl;
	for (int i = 0; i < d.size(); i++) {
		cout << d[i];
	}
	cout << endl;

}

bool check(vector<int> & d, vector<char> &a)
{
	for (int i = 0; i < a.size(); i++) {
		if (a[i] == '<' && (d[i] > d[i + 1]))
			return false;

		if (a[i] == '>' && (d[i] < d[i + 1]))
			return false;
	}
	return true;
}

5. 단어 수학

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

1339번: 단어 수학

풀이의 핵심은 순열을 사용한다!

문자가 몇개인지 체크한 후 높은 숫자부터 할당한 벡터를 하나 가지고 온다.

그리고 그 벡터에 맞춰서 문자의 값을 순열 형태로 돌려가면서 체크(erase 방법 주의)

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
int maxVal = 0;
char alpha[256];

int main() {
	int n;
	cin >> n;

	vector<string> sv(n);
	vector<char> cv;
	for (int i = 0; i < n; i++) {
		cin >> sv[i];
		for (int j = 0; j < sv[i].size(); j++)
			cv.push_back(sv[i][j]);
	}
	
	// 중복제거
	sort(cv.begin(), cv.end());
	cv.erase(unique(cv.begin(),cv.end()), cv.end());

	// 순열 만들기
	vector<int> d;
	for (int i = 0; i < cv.size(); i++)
		d.push_back(9 - i);

	// 확인
	do {
		int val = 0;

		// 할당
		for (int i = 0; i < cv.size(); i++)
			alpha[cv[i]] = d[i];
		
		// 계산
		for (int i = 0; i < sv.size(); i++) {
			int temp_val = 0;
			for (int j = 0; j < sv[i].size(); j++) {
				temp_val = 10 * temp_val + alpha[sv[i][j]];
			}
			val += temp_val;
		}

		// 결과 확인
		if (maxVal < val)
			maxVal = val;

	} while (prev_permutation(d.begin(), d.end()));

	cout << maxVal;
}

6. 스타트와 링크

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

14889번: 스타트와 링크

풀이

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

int main() {
	int N;
	cin >> N;

	vector<vector<int>> a;
	a.assign(N, vector<int>(N, 0));

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> a[i][j];

	vector<int> d(N, 1);
	for (int i = 0; i < N / 2; i++)
		d[i] = 0;
	sort(d.begin(), d.end());

	// Main algorithm
	int min = -1;
	do {
		int ans, team_a = 0, team_b = 0;
		vector<int> ta, tb;
	
		// 0 -> A, 1 -> B
		for (int i = 0; i < a.size(); i++) {
			if (d[i] == 0) 
				ta.push_back(i);

			else 
				tb.push_back(i);
		}

		// 계산
		for (int i = 0; i < N / 2; i++) {
			for (int j = 0; j < N / 2; j++) {
				team_a += a[ta[i]][ta[j]];
				team_b += a[tb[i]][tb[j]];
			}
		}
		ans = abs(team_a - team_b);

		if (min == -1)
			min = ans;

		else if (min > ans)
			min = ans;

	} while (next_permutation(d.begin(), d.end()));

	cout << min;
}