[백준 - 10448] 유레카 이론

#include <bits/stdc++.h>
using namespace std;
#define DP(x) if(dp[x] == 0) dp[x] = x * (x + 1) / 2

int dp[50];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	while (t--)
	{
		int n; cin >> n;

		bool pass = false;
		int result_1 = 0, result_2 = 0, result_3 = 0;

		for (int i = 1; i < 50; ++i)
		{
			DP(i);
			result_1 = dp[i];
			if (n < result_1) break;

			for (int j = 1; j < 50; ++j)
			{
				DP(j);
				result_2 = dp[j];
				if (n < result_1 + result_2) break;

				for (int k = 1; k < 50; ++k)
				{
					DP(k);
					result_3 = dp[k];
					if (n < result_1 + result_2 + result_3) break;

					if (result_1 + result_2 + result_3 == n)
					{
						pass = true;
						break;
					}
				}
				if (pass == true) break;
			}
			if (pass == true) break;
		}
		cout << (pass ? "1" : "0") << '\n';
	}
	return 0;
}

---

||사고 과정

먼저 가장 쉽게 생각 할 수 있는 완전 탐색이 가능한지 생각했다.

3중 for문으로 O(n^3)을 예상하여 n의 최대 값을 대략 구해보려했다.

 

구하려는 수k는 최대 1000이므로

1000 = n * (n + 1) / 2  → 2000 = n * (n + 1) 이다.

대략적으로 2000 = n^2이라 치면

 

n이 100일때 k는 10000

n이 50일때 k는 2500

 

고로 넉넉하게 n을 50이라 생각하면 50^3 = 125,000으로 1초안에 충분히 결과가 나올 수 있을것 같았다.

 

삼각수는 dp배열에 저장하여 다시 계산하지 않도록 연산을 생략했다.

---

||사용 기법

• Brute Force
• Dp

---

||다른 풀이

이건 백트래킹을 이용해 봤다.

#include <bits/stdc++.h>
using namespace std;

#define MAX 50
#define DP(x) if(dp[x] == 0) dp[x] = x * (x + 1) / 2

int dp[MAX];

//total:누적 값, i : 삼각수 번호, len : 재귀의 길이 (one index), n : 찾는 값
bool BT(int total, int i, int len, int n)
{
	if (3 < len) return false;
	
	DP(i);
	total += dp[i];
	if (total == n && len == 3) return true;
	if (n < total) return false;

	for (int k = 1; k < MAX; ++k)
	{
		if(BT(total, k, len + 1, n) == true) return true;
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	while (t--)
	{
		int n; cin >> n;
		cout << (BT(0,0,0,n) ? "1" : "0") << '\n';
	}
	return 0;
}

 

혹은 DP를 다 채우고 하는 사람도 많았다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int dp[MAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	for (int i = 1; i < MAX; ++i)
	{
		dp[i] = i * (i + 1) / 2;
	}

	while (t--)
	{
		int n; cin >> n;

		bool pass = false;
		for (int i = 1; i < 50; ++i)
		{
			for (int j = 1; j < 50; ++j)
			{
				for (int k = 1; k < 50; ++k)
				{
					if (dp[i] + dp[j] + dp[k] == n) pass = true;
				}
			}
		}

		cout << (pass ? "1" : "0") << '\n';
	}
	return 0;
}

 

혹은 bool을 만들어서 아에 세가지가 될 수 있는 경우를 모두 저장하여 마지막에 바로바로 출력한다

여러 테스트 케이스가 있다면 이렇게 한번에 채우고 가는게 훨씬 좋은것 같다.

시간복잡도가 훨씬 줄어들었다.

내 생각엔 이 코드가 최고인것 같다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int dp[MAX];
bool b[125000];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	for (int i = 1; i < MAX; ++i)
	{
		dp[i] = i * (i + 1) / 2;
	}
	
	for (int i = 1; i < MAX; ++i)
	{
		for (int j = 1; j < MAX; ++j)
		{
			for (int k = 1; k < MAX; ++k)
			{
				b[dp[i] + dp[j] + dp[k]] = true;
			}
		}
	}

	while (t--)
	{
		int n; cin >> n;
		cout << b[n] << '\n';
	}
	return 0;
}

이렇게 필요 없는 코드를 줄여보니까 어떻게 줄여야할지 좀 알았고 담에 좀 더 신경 써야겠다.