브루트포스란

가장 간단한 알고리즘인, 모든 경우의 수를 검사하는 브루트 포스 알고리즘이다.

2231

2231번 : 분해합

#include <iostream>
using namespace std;

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

	int num = 0;

	int size, sum;
	for (int i = 1; i < N; i++) {
		sum = i;
		size = i;

		while(size) {
			sum = sum + (size % 10);
			size = size / 10;
		}
		
		if (sum == N) {
			cout << i;
			return 0;
		}
	}

	cout << "0" << endl;
	return 0;
}

입력받은 N값보다 작은 값들을 모두 분해값으로 계산하여 N값과 일치하는 합이 나온다면 출력한다.

2798

2798번 : 블랙잭

#include <iostream>
using namespace std;

int main() {
	int N, M;
	int num[100];
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	int result = 0;
	int i = 0, j = 1, k = 2;

	for (i = 0; i < N - 2; i++) {
		for (j = i + 1; j < N - 1; j++) {
			for (k = j + 1; k < N; k++) {
				if (num[i] + num[j] + num[k] <= M && (num[i] + num[j] + num[k]) > result)
					result = num[i] + num[j] + num[k];
			}

		}
	}

	cout << result;
}

입력된 모든 숫자들 중 3개만을 뽑아내기 위해 순서대로 3중포문을 돌려 차례대로 더해준다. 이때 첫번째 선택지인 i 는 뒤에 선택될 두가지를 비워두어야 하므로 N-2까지, 두번째 선택지인 j는 뒤에 선택될 한가지를 위해 N-1까지, 마지막으로 선택될 k 선택지는 N까지 범위를 설정한다.

7568번 : 덩치

처음에는 rank 를 제일 뒤부터 설정하여, 덩치가 더 큰 사람이 나타나면 해당 랭크를 1씩 낮추는 방식으로 진행했다.

그렇게 하니, 반례가 발생하였다.

만약

3
1 2
2 2
3 4

를 입력하게 되면 등수는 2 2 1이 출력되어야 하지만,

내가 처음 설정한 알고리즘을 이용하면 3 3 1이 출력된다.

올바르게 등수가 정렬되지 않는것이다.

따라서 완벽히 더 큰 덩치의 사람이 나왔을때만 작은 덩치의 사람 등수를 낮춘다면 올바른 정렬이 가능할 것이다.

#include <iostream>
using namespace std;

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

	int x[50], y[50];
	int rank[50];
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
		rank[i] = N;
	}

	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (x[i] < x[j] && y[i] < y[j])
				rank[j]--;
			else if (x[i] > x[j] && y[i] > y[j])
				rank[i]--;
			else {
				if (x[i] < x[j] && y[i] > y[j]) {
					rank[j]--;
					rank[i]--;
				}
				else if (x[i] > x[j] && y[i] > y[j]) {
					rank[j]--;
					rank[i]--;
				}
			}

		}
	}


	for (int i = 0; i < N; i++) 
		cout << rank[i] << " ";

}

최종

#include <iostream>
using namespace std;

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

	int x[50], y[50];
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
	}

	
	int k = 0;
	for (int i = 0; i < N; i++) {
		k = 0;
		for (int j = 0; j < N; j++) {
			if (x[i] < x[j] && y[i] < y[j])
				k++;
		}
		cout << k + 1 << " ";
	}
}