(백준 10448번 유레카 이론 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 2탄

차근차근 라이님 블로그에 있는 완전탐색 문제를 뽀개보기로 했다. 완전 탐색 1탄은 아래로!

 

2023.12.18 - [알고리즘] - 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search)

라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search)

 

백준 10448번 유레카이론

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

10448번: 유레카 이론

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

bool IsTriNum(int num, int * arr) {
	int sum = 0;
	for (int i = 0; i < 50; i++) {
		for (int j = 0; j < 50; j++) {
			for (int k = 0; k < 50; k++) {
				sum = arr[i] + arr[j] + arr[k];
				if (num == sum) return true;
				else if(sum > num) break; /// sum과 num의 자리를 바꿔 적어놔서 디버깅 1시간 했다..ㅠ
			}
		}
	}
	return false;
}


int main() {
	int cnt;
	int arr[50];
	scanf("%d", &cnt);
	int* input = new int[cnt];

	///arr에 1000이하 삼각수 채워넣기
	for (int i = 0; i < 50; i++) arr[i] = (i+1) * (i + 2) / 2;
	for (int j = 0; j < cnt; j++) scanf("%d", &input[j]);
	for (int k = 0; k < cnt; k++) printf("%d\n", IsTriNum(input[k], arr));
	
	delete[]input;
	return 0;
}

문제 풀이 방향은 완전탐색 문제인 만큼 심플하다.

1. 삼각수를 int 배열안에 넣는다. (입력되는 숫자는 1000이하 이므로 삼각수도 50개만 배열 안에 넣었다)

참고로 50번째 삼각수 T50 = 50 * 51 / 2 = 1275이다.

2. 삼중 for loop을 이용해 세 개의 삼각수로 표현되는지 확인한다.

 

🌻다른풀이🌻

 (과거의 내 풀이) bool형 array[5000]를 check리스트로 두고, 삼중 for loop을 돌면서 세 삼각수의 합으로 표현되는 숫자에 해당하는 칸을 true로 바꾼다.그리고 입력된 값에 대응하는 array의 bool 값을 확인한다.