[アルゴリズム-問題]ブルートフォース
ブルートフォースはすべての状況で試します.
問題1)7人の小人[2309]
の関数(非作成のようです) が追加作成されました.を格納するために新しい配列(arr 2)が作成された(新しく作成された配列はソートのためであり、これは7人の小人が判別する前に予めソートする方法がある) .の新しいパラメータ(c sum)が作成されました(これは大きなスペースを占有するエラーではありませんが、簡単な場合、新しいパラメータを作成する必要はないようです) forと書いてあるドア内はすぐに戻ります(flagを追加して見つけたらflagを追加すると、ドアの脱出にはもっとスムーズになるようです) コードの変更)問題2)キャンディゲーム[3085]
check関数を作成し、コード作成を簡略化する swap関数 行と列 ベクトルを使用すると便利 覚えておく)ベクトルの使い方を熟知している
https://velog.io/@soddong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-c-vector 問題3)計算日[1476]
は必ず丁寧に近づかなければなりません!私の場合、modを使うために1を外すべきでしたが、1が漏れてしまいました...よく考えなさい. 問題4)リモコン[107]
アレイでは、(dx,dy)方式ですべてのエンクロージャを保存する方法が非常に有用である. ブルートフォスは最初から最後までブラウズしているだけです!とみなす
問題1)7人の小人[2309]
ジュニア9人のうち、合計100人のジュニア7人を探す.
時間の複雑さ:O(N 2)、状況の数:9 C 2=36->だから全部やってみてもいいですよ~
プリコード)void print(int* arr, int fake, int fake2) {
int arr2[7];
int j = 0;
for (int i = 0; i < 9; i++){
if ((arr[i] != arr[fake]) && (arr[i] != arr[fake2])) {
arr2[j] = arr[i];
j++;
}
}
for (int i = 0; i < 7; i++) {
sort(arr2, arr2 + 7);
cout << arr2[i] << "\n";
}
}
int main() {
int a[9];
int sum = 0;
int c_sum = 0;
for (int i = 0; i < 9; i++) { // 난쟁이의 키 입력받기
scanf("%d", &a[i]);
sum += a[i];
}
for (int i = 0; i < 8; i++) { // 모든 경우의 수
for (int j = 1 + i; j < 9; j++) {
c_sum = a[i] + a[j];
if (sum - c_sum == 100) {
print(a, i, j); // 찾은 경우, 출력하는 함수 호출
return 0;
}
}
}
return 0;
}
コードの無効な点)
出力
void print(int* arr, int fake, int fake2) {
int arr2[7];
int j = 0;
for (int i = 0; i < 9; i++){
if ((arr[i] != arr[fake]) && (arr[i] != arr[fake2])) {
arr2[j] = arr[i];
j++;
}
}
for (int i = 0; i < 7; i++) {
sort(arr2, arr2 + 7);
cout << arr2[i] << "\n";
}
}
int main() {
int a[9];
int sum = 0;
int c_sum = 0;
for (int i = 0; i < 9; i++) { // 난쟁이의 키 입력받기
scanf("%d", &a[i]);
sum += a[i];
}
for (int i = 0; i < 8; i++) { // 모든 경우의 수
for (int j = 1 + i; j < 9; j++) {
c_sum = a[i] + a[j];
if (sum - c_sum == 100) {
print(a, i, j); // 찾은 경우, 출력하는 함수 호출
return 0;
}
}
}
return 0;
}
/* 2309번 일곱난쟁이 */
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int a[9];
int sum = 0, flag = 0;
for (int i = 0; i < 9; i++) { // 난쟁이의 키 입력받기
scanf("%d", &a[i]);
sum += a[i];
}
sort(a, a + 9);
for (int i = 0; i < 8; i++) { // 모든 경우의 수
if (flag == 1) break;
for (int j = 1 + i; j < 9; j++) {
if (flag == 1) break;
if (sum - (a[i] + a[j]) == 100) {
flag = 1;
for (int k = 0; k < 9; k++) {
if (k != i && k != j)
cout << a[k] << "\n";
}
}
}
}
return 0;
}
問題2)キャンディゲーム[3085]
時間通りに答えられなかったので、白準の答えを参考にしました.
)/* 3085번 사탕게임 */
#include <iostream>
#include <stdio.h>
#include <vector>
#define N 50
using namespace std;
int check(vector<string> &ca, int n) { // 모든 행과 열을 조사하여 연속하는 수의 최대값을 구함
int max_cnt = 0;
for (int i = 0; i < n; i++) {
int cnt = 1;
for (int j = 0; j < n-1; j++) {
if (ca[i][j] == ca[i][j+1]) cnt++;
else {
cnt = 1;
}
max_cnt = max(cnt, max_cnt);
}
cnt = 1;
for (int j = 0; j < n-1; j++) {
if (ca[j][i] == ca[j + 1][i]) cnt++;
else {
cnt = 1;
}
max_cnt = max(cnt, max_cnt);
}
}
return (max_cnt);
}
int main() {
int n;
cin >> n;
// 입력 받기
vector<string> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
int m_candy = 0, ans = 0;
for (int i = 0; i < n; i++) { // 모든 행, 열에 대하여 swap => check함수를 호출하여 최대연속수 리턴
for (int j = 0; j < n; j++) { // 행
if (i < n - 1) {
swap(c[i][j], c[i + 1][j]);
m_candy = check(c, n);
ans = max(m_candy, ans);
swap(c[i][j], c[i + 1][j]);
}
if (j < n - 1) { // 열
swap(c[i][j], c[i][j + 1]);
m_candy = check(c, n);
ans = max(m_candy, ans);
swap(c[i][j], c[i][j + 1]);
}
}
}
cout << ans << "\n";
return 0;
}
コード効率)
個別の
/* 3085번 사탕게임 */
#include <iostream>
#include <stdio.h>
#include <vector>
#define N 50
using namespace std;
int check(vector<string> &ca, int n) { // 모든 행과 열을 조사하여 연속하는 수의 최대값을 구함
int max_cnt = 0;
for (int i = 0; i < n; i++) {
int cnt = 1;
for (int j = 0; j < n-1; j++) {
if (ca[i][j] == ca[i][j+1]) cnt++;
else {
cnt = 1;
}
max_cnt = max(cnt, max_cnt);
}
cnt = 1;
for (int j = 0; j < n-1; j++) {
if (ca[j][i] == ca[j + 1][i]) cnt++;
else {
cnt = 1;
}
max_cnt = max(cnt, max_cnt);
}
}
return (max_cnt);
}
int main() {
int n;
cin >> n;
// 입력 받기
vector<string> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
int m_candy = 0, ans = 0;
for (int i = 0; i < n; i++) { // 모든 행, 열에 대하여 swap => check함수를 호출하여 최대연속수 리턴
for (int j = 0; j < n; j++) { // 행
if (i < n - 1) {
swap(c[i][j], c[i + 1][j]);
m_candy = check(c, n);
ans = max(m_candy, ans);
swap(c[i][j], c[i + 1][j]);
}
if (j < n - 1) { // 열
swap(c[i][j], c[i][j + 1]);
m_candy = check(c, n);
ans = max(m_candy, ans);
swap(c[i][j], c[i][j + 1]);
}
}
}
cout << ans << "\n";
return 0;
}
https://velog.io/@soddong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-c-vector
問題3)計算日[1476]
問題を解決する前に、Broutforceで解決できる問題かどうかを判断することが重要です.
そこで、この問題の状況を考えてみると、
1<=E<=15,1<=S<=28,1<=M<=19であるため、全ての場合の数字は152819である.見るとすべてのバンジージャンプを試してみることができます.
覚えておく)
問題4)リモコン[107]
この問題はやっていたが、結局方向が見つからず、できなかった.
この問題のように、方法がわからなければBroutforceを使います!
問題を解くときに重要なのはアルゴリズムの手順を分類することです!
だから、この問題に対して、
1.一番近いチャンネルを移動(番号別)
2.ターゲットチャンネルに移動(+/-)
問題5)トロミノ[14500]
ああ...5つ目は再検討した問題ですううう
ブルートフォースの問題は非常に注意しなければならない.
覚えておく)
ああ...5つ目は再検討した問題ですううう
ブルートフォースの問題は非常に注意しなければならない.
覚えておく)
Reference
この問題について([アルゴリズム-問題]ブルートフォース), 我々は、より多くの情報をここで見つけました https://velog.io/@soddong/알고리즘-문제-브루트포스テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol