[BOJ] 10448 유레카 이론 C++

문제

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

 

풀이

가장 중요한 건 몇 번째 삼각수까지 볼 것인가인 거 같다. 45*46/2=1035이므로 45보다 큰 수가 들어가면 최대 수인 1000을 맞추지 못한다. 다른 풀이에서는 45까지의 삼각수를 모두 배열에 입력해둔 뒤 3중 for문으로 i, j, k 3개의 수를 선택하는 경우를 표현한 코드도 있었다.

 

코드

#include <iostream>
#include <vector>

using namespace std;


vector<int> v;
bool isSatisfied;

// 삼각수 공식: Tn = n(n+1)/2
bool check(int testNum){
    int sum = 0;
    for(int e : v){
        sum += e*(e+1)/2;
    }
    return sum==testNum;
}

void backtracking(int curr, int testNum){
    // 종료 조건(3개의 삼각수의 합으로 표현)
    if(v.size()==3){
        if(check(testNum)){
            isSatisfied = true;
        }
        return;
    }

    // 만족하는 정답이 있다면 더 탐색하지 않음
    if(isSatisfied) return;

    // 재귀 호출
    for(int i=1; i<=45; i++){ // 45*46/2=1035
        v.push_back(i);
        backtracking(curr+1, testNum);
        v.pop_back();
    }
}

// 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력
int main(){
    int tc = 0;
    cin >> tc;
    while(tc--){
        // 자연수 K (3 ≤ K ≤ 1,000)
        int testNum = 0;
        cin >> testNum;

        isSatisfied = false;

        backtracking(0, testNum);

        if(isSatisfied) cout << 1 << '\n';
        else cout << 0 <<'\n';
    }

    return 0;
}