백준 문제 10448번 유레카 이론

문제 출처:

www.acmicpc.net/problem/10448

10448번: 유레카 이론

 

백준 10448번 문제- 유레카 이론

 

우선 이 문제를 보고 그냥 다 더해보는 수 밖에 없겠는데? 라는 생각이 들었다. 

조금 무식한 방법이기는 하지만 딱히 별다른 바가 생각나지 않았기 때문에 T에 해당하는 원소들을 다 뽑아서 vector에 넣어주고 시간복잡도가 $n^4$ 가 되기는 하지만 우선 구현해보자는 목적하나에 만들어 보았다. 

#include <iostream>
#include <vector>

using namespace std;

int match(vector <short> & K, int target);

int main(){
    ios::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);
    // K (3 ≤ K ≤ 1,000)    Tn = n(n+1)/2 
    unsigned short T ;
    
    cin >> T ;

    vector <short> K ;
    
    short k ;
    for(int i = 1 ; k <= 1000; i++){
        k = i*(i+1)/2 ;
        if(k > 1000)
            break ;
        
        K.push_back(k) ;
    }
    
    vector <int> result ;

    int target ;
    for(int n = 0 ; n < T; n++){
        cin >> target ;
        result.push_back(match(K, target)) ;
    }

    for(int i = 0 ; i < result.size() ; i++){ 
        cout << result[i] << endl ;
    }

    return 0 ;
}

int match(vector <short> & K, int target){

    int sum = 0 ;
    for(int i = 0 ; i < K.size() ; i++){
        for(int j = 0 ; j < K.size() ; j++){
            for(int k = 0 ; k < K.size() ; k++){
                sum = K[i] + K[j] + K[k] ;
                if(target == sum)
                    return 1 ;
            }
        }
    }
    return 0 ;
}

 

위와 같은 코드로 구현하였으며, 문제 없이 돌아가는 것을 확인했다.

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P10448_Eureka.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

 

훈수, 조언 언제나 환영입니다.