[BF] 10448번 유레카 이론

10448번 유레카 이론

 

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

 

문제

삼각수 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

 

해결방법

모든 경우를 다 해보는 완전탐색 문제이다

 

이 문제를 보고 가장 먼저 소수문제와 유사하게 접근하면 되겠다고 생각했다

소수 문제는 먼저 에라토스테네스의 체 를 사용하여 소수를 미리 구하고 다른 작업을 수행한다

이 문제 또한 삼각수를 먼저 구하고 이를 이용해 문제를 풀면 된다고 생각했다

 

k ≤ 1,000 인데 모든 삼각수를 구해보면 그리 많지 않기 때문에 시간 초과가 발생하지 않는다

 

⭐️ 솔루션 ⭐️

• 삼각수를 벡터에 집어 넣는다
• 입력받은 값과 cnt 값을 매개변수로한 dfs 함수를 호출한다
• 삼각수 벡터를 돌며 현재 값보다 작은 값들에 한해 재귀 함수를 호출한다 (값 - 삼각수)
• cnt 값이 3개가 되었을 때, num == 0 이라면 이 수는 삼각수이므로 flag 를 true로 설정한다
• 만약 num != 이라면 이 수는 삼각수가 아니므로 return 해준다

 

 

⭐️ 다른 방법 ⭐️

• 삼각수를 벡터에 집어 넣는다
• 이를 이용해 3중 for문을 작성한다
• 3개의 삼각수가 골라졌을 때, n과 비교해서 같으면 flag를 true 로 설정해준다

 

 

이 코드는 break 조건을 넣은 경우와 안넣은 경우인데 경우가 많이 없다보니 시간차이가 거의 나지 않았다

for(int i=0; i<triNumber.size(); i++){
    for(int j=0; j<triNumber.size(); j++){
        for(int k=0; k<triNumber.size(); k++){
            if(triNumber[i]+triNumber[j]+triNumber[k] == n){
                flag = true;
            }
        }
    }
}

for(int i=0; i<triNumber.size(); i++){
    if(triNumber[i] > n) break;
    for(int j=0; j<triNumber.size(); j++){
        if(triNumber[j] > n) break;
        for(int k=0; k<triNumber.size(); k++){
            if(triNumber[k] > n) break;
            if(triNumber[i]+triNumber[j]+triNumber[k] == n){
                flag = true;
                break;
            }
        }
        if(flag) break;
    }
    if(flag) break;
}

 

 

 

소스코드

[ DFS 코드 ]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;

int testcase,n;
bool flag;

vector<int> triangularNumber;

void getTriangularNumber(){
    int i = 1;
    while(true){
        int cal = i*(i+1) / 2;
        
        if(cal >= MAX) break;
        
        i++;
        triangularNumber.push_back(cal);
    }
}

void dfs(int num,int cnt){
    if(cnt == 3){
        // 3개의 삼각수로 값이 이뤄진 경우
        if(num == 0){
            flag = true;
            return;
        }
        // 3개의 삼각수로 값이 이뤄지지 않은 경우
        else{
            return;
        }
    }
    
    for(int i=0; i<triangularNumber.size(); i++){
        // 현재 값보다 큰 수는 X
        if(triangularNumber[i] > num) return;
        
        dfs(num-triangularNumber[i],cnt+1);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 삼각수 구하기
    getTriangularNumber();
    
    cin >> testcase;
    for(int t=0; t<testcase; t++){
        cin >> n;
        
        flag = false;
        dfs(n,0);
        
        if(flag) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
    
    return 0;
}

 

[ 3중 for문 ]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;

int testcase,n;
bool flag;

vector<int> triNumber;

void getTriNumber(){
    int i = 1;
    while(true){
        int cal = i*(i+1) / 2;
        
        if(cal >= MAX) break;
        
        i++;
        triNumber.push_back(cal);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 삼각수 구하기
    getTriNumber();
    
    cin >> testcase;
    for(int t=0; t<testcase; t++){
        cin >> n;
        
        flag = false;
        
        for(int i=0; i<triNumber.size(); i++){
            if(triNumber[i] > n) break;
            for(int j=0; j<triNumber.size(); j++){
                if(triNumber[j] > n) break;
                for(int k=0; k<triNumber.size(); k++){
                    if(triNumber[k] > n) break;
                    if(triNumber[i]+triNumber[j]+triNumber[k] == n){
                        flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
        
        if(flag) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
    
    return 0;
}