[백준 10448 c++] 유레카 이론

문제 링크

www.acmicpc.net/problem/10448

10448번: 유레카 이론

문제 접근

// 접근: 3개의 합으로 되는지 아닌지만 구별 -> 3중 반복문으로 완전탐색

// 하지만 4중 반복으로 해야 모든 테스트 케이스를 돌 수 있다.

 

 

 

 

 

 

 

 

 

 

문제 풀이

// 풀이: 런타임 초과 날까봐 t의 최대값이 1000=i(i+1)/2 를 이용 500 까지만 반복하게 함

 

 

 

 

 

 

 

 

 

 

 

 

주의

 

 

 

 

개념

 

 

 

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 10448 c++] 유레카 이론
// 접근: 3개의 합으로 되는지 아닌지만 구별 -> 3중 반복문으로 완전탐색
// 하지만 4중 반복으로 해야 모든 테스트 케이스를 돌 수 있다. 
// 풀이: 런타임 초과 날까봐 t의 최대값이 1000=i(i+1)/2 를 이용 500 까지만 반복하게 함
// 

using namespace std; // cin,cout 편하게 사용 라이브러리

#define MAX 50
int n;
vector<int> v;

int main()
{
	// IO 속도 향상
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int tp;
		cin >> tp;
		v.push_back(tp);
	}
	for (int p = 0; p < n; p++)
	{
		int c = 0;
		for (int i = 1; i < 500; i++)
		{
			
			for (int j = 1; j < 500; j++)
			{
				for (int q = 1; q < 500; q++)
				{
					if (i * (i + 1) / 2 + j * (j + 1) / 2 + q * (q + 1) / 2 == v[p])
					{
						c++;
						// 3중 반복 끝내기
						q = 500;
						j = 500;
						i = 500;

					}
				}
			}
		}
		cout << c << '\n';
	}
	return 0;
}