[백준] 유레카 이론

■ 문제

 

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1 + T2

• 5 = T1 + T1 + T2

• 6 = T2 + T2 or 6 = T3

• 10 = T1 + T2 + T3 or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

 

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

 

■ 입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

 

■ 출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

 

■ 예제

입력	출력
3 10 20 1000	1 0 1

 

▶ 코드

 

문제를 해결한 프로세스는 다음과 같다.

 

1. 삼각수로만 구성된 vector를 만든다. 

vector<int> eureka;

...

void make_Eureka(){
	int sum =0;
	for(int i=1;;i++){
		if(sum >1000) break;
		sum+=i;
		eureka.push_back(sum);
	}
}

2. 구성 가능한 수들을 담는 vector를 만든다. (자기 자신보다 작은수로만 구성 될 수 있음)

vector<int> consist;

...

for(int i=0;;i++){
	if(eureka[i] < k)
		consist.push_back(eureka[i]);		
	else
	    break;
}

3. 구성 가능한 수를 담는 vector에서 숫자 3개로 중복 가능한 순열을 모두 구하고,

만약 있다면 1을 return하고 그렇지 않다면 0을 return한다.

void dfs(int n){
	if(n==3){
		for(int i=0;i<3;i++)
			count+=arr[i];
			
		if(count==k)
			result = true;
		else 
			count = 0;
	}else{
		for(int i=0;i<consist.size();i++){
			arr[n] = consist[i];
			dfs(n+1);
		}
	}
}

 

전체 코드는 아래와 같다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> eureka;
vector<int> consist;
int count =0;
bool result = false;
int k;

int arr[3];

void make_Eureka(){
	int sum =0;
	for(int i=1;;i++){
		if(sum >1000) break;
		sum+=i;
		eureka.push_back(sum);
	}
}

void dfs(int n){
	if(n==3){
		for(int i=0;i<3;i++)
			count+=arr[i];
			
		if(count==k)
			result = true;
		else 
			count = 0;
	}else{
		for(int i=0;i<consist.size();i++){
			arr[n] = consist[i];
			dfs(n+1);
		}
	}
}

void solution(){
	
	for(int i=0;;i++){
		if(eureka[i] < k){
			consist.push_back(eureka[i]);
		}		
		else
			break;
	}
	
	dfs(0);
	
	cout << result<<endl;
	
	consist.clear();
	result = false;
	
}

int main(){
	
	//input
	int t;
	cin >> t;
	
	//삼각수 배열 만들기
	make_Eureka(); 
	

	for(int i=0;i<t;i++){
		cin >> k;
		solution();
	}
	
	return 0;
}

 

※ 출처 : https://www.acmicpc.net/problem/10448

10448번: 유레카 이론