(백준 2309번 일곱난쟁이 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 1탄

개념이 매우 간단한 완전탐색! Brute-force Search라고 하는게 더 멋있는거 같은 느낌의 탐색 방법이다.

시간복잡도 때문에 자주 쓰이지는 않지만 기본 알고리즘에 속하기 때문에 꼭 알고가야 하는 알고리즘!

 

(혹시 저작권에 문제가 있다면 수정하겠습니다!! 개인적인 공부용으로 정리함을 알려드립니당)

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220769870195&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

완전 탐색(Brute-force Search)

 

백준 2309번 - 일곱 난쟁이 문제

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int arr1[10], arr2[10];
int sum_9 = 0, sum_7 = 0;
int idx1 = -1, idx2 = -1;
void Swap(int * a, int * b);

int main() {
	for (int i = 0; i < 9; i++) {
		scanf("%d", &arr1[i]);
		sum_9 += arr1[i];
	}
	for (int i = 0; i < 9; i++) {
		for (int j = i+1; j < 9; j++) {
			sum_7 = sum_9 - arr1[i] - arr1[j];
			if (sum_7 == 100) {
				idx1 = i, idx2 = j;
				break;
			}
		}
		if (idx1 > 0) break;
	}
	int num = 0;
	for (int i = 0; i < 9; i++) {
		if (i == idx1 or i == idx2) continue;
		arr2[num] = arr1[i];
		num++;
	}
	for (int i = 0; i < 7; i++) {
		for (int j = i; j < 7; j++) {
			if (arr2[j] < arr2[i]) Swap(&arr2[j], &arr2[i]);
		}
	}

	for (int i = 0; i < 7; i++) printf("%d\n", arr2[i]);
	return 0;
}

void Swap(int * a, int * b) {
	int temp = *a;
	*a = *b; 
	*b = temp;
}

미리 sorting해놓고 두 개의 인덱스를 골랐으면 풀이가 더 간단하지 않았을까 싶다.. 

 

ㅋㅋㅋㅋㅋㅋㅋ3년 전의 나.. 꽤나 똑똑했구나!

⭐다른 풀이

다른 사람들 풀이는 보니 Bool형 array[100]을 만들어서 풀었다.

문제 예시로 보면 20, 7, 23, 19, 10, 15, 25, 8, 13의 값에 대응해서 array[i] = True로 만들고

전체 합(이 문제에서는 140)에서 100을 뺀 숫자(40)이 되도록 하는 두 숫자를 찾는 방식이다.

arrar[15] = True이고, array[40-15] = True이므로 15와 45를 제외한 숫자를 출력하면 된다.

(오,, 심박한 방법이다. 난쟁이 키가 모두 다르니때문에 중복의 문제는 없다!) 

 

그리고 '23.12.18. 현재 백준 #1912번 안 풀린다..ㅠ 진짜 뇌가 굳었나..ㅠㅠ흙흙