이것 저것 &

문제링크:https://www.acmicpc.net/problem/11502

에라토스테네스의 체 알고리즘을 알고있어야합니다.

아래코드입니다.

for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 1) continue;
		for (int j = i + i; j <= 1000; j += i)
			arr[j] = 1;
	}
	

소수의 배수는 소수가 아닌 것을 이용해서 소수에는 0 비소수에는 1을 넣어놓습니다. 

그이후 O(n^3)만큼 삼중포문으로 반복하면서 값을 판별해주는 완전탐색문제 (브루트 포스) 였습니다. 

구현이 너무 쉽기때문에  나머지 설명은 생략하겠습니다.

정답코드입니다. 

#include <iostream>
using namespace std;
int t = 0, n = 0;
int arr[1001] = { 0 };


int main() {
	for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 1) continue;
		for (int j = i + i; j <= 1000; j += i)
			arr[j] = 1;
	}
	
	cin >> t;
	while (t--) {
		bool jud = false;
		cin >> n;
		for (int i = 2; i <= n; i++) {
			if (arr[i] == 1) continue;
			for (int j = 2; j <= n; j++) {
				if (arr[j] == 1) continue;
				for (int k = 2; k <= n; k++) {
					if (arr[k] == 1) continue;

					if ((i + j + k) == n) {
						cout << i << ' ' << j << ' ' << k << endl;
						jud = true;
						break;
					}
				}
				if (jud == true)
					break;
			}
			if (jud == true)
				break;
		}
	
	}
}

문제링크: https://www.acmicpc.net/problem/1251

모든 경우의 수를 비교해봐야하는 브루트 포스 문제입니다.

즉, 완전탐색을 하는 것입니다.

비교적 쉬운 난이도였지만, 틀리기 좋았던 부분은 단어를 쪼갤때

1. 삼등분을 해야하기 때문에 중복이 되면 안된다.

2. 세가지 덩어리가 순서대로 돌아와야한다.

오답코드가 있으시다면 해당 테스트케이스를 확인해보세요.

afbdba -> abdbfa

정답코드입니다.

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

string input,result;
string a, b;

int main() {
	cin >> input;

	result = "{"; 

	for (int i = 0; i < input.size()-2; i++) {
		for (int j = i+1; j < input.size()-1; j++) {
			
			string val;

			for (int u = i; u >= 0; u--)
				val += input[u];

			for (int u = j; u > i; u--)
				val += input[u];

			for (int u = input.size() - 1; u > j; u--)
				val += input[u];

			if (result > val) result = val;
			
		}
		
	}


	cout << result << endl;
}

문제링크: https://www.acmicpc.net/problem/1051

브루트포스 문제입니다. 모든 점에서 꼭짓점값들을 확인해서 가장크게 만들 수 있는 정사각형 넓이를 출력하는 문제였습니다. 정답률이 30퍼때라 좀 어려울 줄 알았는데 생각보다 너무 쉬워서 놀랐습니다.

각 점에서 오른쪽과 아래로 내려갈 수 있는 값들을 고려하면서 값을 도출합니다.

코드가 너무 쉬워서 설명은 생략하겠습니다. :)

아래는 정답코드입니다. 

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

int n, m, result = 1;
int arr[51][51] = { 0 };
string input;

int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
			cin >> input;
			for (int j = 0; j < input.size(); j++)
				arr[i][j] = input[j] - '0';
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int k = 1;; k++) {
				if ((j + k) >= m || (i + k) >= n) break;
				if (arr[i][j] == arr[i][j + k] && arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i + k][j + k])
					if(cnt < k)
						cnt = k;
			}
			if ((cnt + 1) > result) result = cnt + 1;
		}

	}

	cout << result * result << endl;
}

문제링크:https://www.acmicpc.net/problem/2966

전형적인 브루트포스문제였습니다.

어렵지 않았을 것이라고 생각합니다.

너무 쉬운문제라서 설명은 생략하겠습니다.

#include <iostream>
using namespace std;

char a[3] = { 'A','B','C' };
char b[4] = { 'B','A','B','C' };
char c[6] = { 'C','C','A','A','B','B' };
char arr[101];
int cnt[3] = { 0 };

int n = 0, result = 0;

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

	for (int i = 0; i < n; i++) {
		if (a[i % 3] == arr[i]) cnt[0]++;
		if (b[i % 4] == arr[i]) cnt[1]++;
		if (c[i % 6] == arr[i]) cnt[2]++;
	}
	for (int i = 0; i < 3; i++)
		if (result < cnt[i]) result = cnt[i];
	cout << result << endl;
	if (cnt[0] == result) cout << "Adrian" << endl;
	if (cnt[1] == result) cout << "Bruno" << endl;
	if (cnt[2] == result) cout << "Goran" << endl;
}

문제링크:https://www.acmicpc.net/problem/2503

모든 경우를 고려해주며 결과값을 도출하는 브루트포스 문제였습니다.

숫자의 범위가 적기 때문에 어려운 점은 없는 문제였습니다.

1) 100~999까지의 수를 반복하며 확인 

2) 이때 0을 포함, 혹은 같은 자릿수를 가지는 수는 제외

3) 같은 자릿수를 가지면 strike값을 올리고 다른 자리에 해당 값이 있다면 ball값을 올려줍니다.

4) 조건을 만족하는 수가 있다면 결과값을 +1씩 올려줍니다.

2번조건을 간과해서 틀릴 수 있습니다. 문제조건을 한번더 확인하는 습관을 가져야겠습니다.

직접문제를 풀어보세요! :0 화이팅

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0, result = 0;
int arr[100][3] = { 0 };
int arr2[9] = { 0 };
int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	for (int i = 100; i <= 999; i++) {
		if (i % 10 == 0) continue; //0 안들어가게
		if ((i / 10) % 10 == 0) continue;

		if (i / 100 == (i / 10) % 10) continue;
		if (i / 100 == i % 10) continue;
		if (i % 10 == (i / 10) % 10) continue;
		bool jud = true;

		for (int j = 0; j < n; j++) {
			for (int k = 1; k <= 9; k++) arr2[k] = 0;
			bool first = false, second = false, third = false;

			int strike = 0, ball = 0;
			int num = i;
			
			if (num / 100 == arr[j][0] / 100) strike++,first=true;
			arr2[arr[j][0] / 100]++;

			if ((num / 10) %10 == (arr[j][0] / 10)%10) strike++,second=true;
			arr2[(arr[j][0] / 10) % 10]++;

			if (num % 10 == arr[j][0] % 10) strike++,third=true;
			arr2[arr[j][0] % 10]++;
			
			if (!first&&arr2[num / 100]) ball++;
			if (!second&&arr2[(num / 10) % 10]) ball++;
			if (!third&&arr2[num % 10]) ball++;

			if (strike != arr[j][1] || ball != arr[j][2]) {
				jud = false;
				break;
			}

		}
		if (jud == true) {
			
			result++;
		}
	}
	cout << result << endl;
	return 0;
}