백준 10448 - 유레카 이론

C++

10448번 - 유레카 이론

문제

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

접근 방법

이 문제는 2가지의 방법으로 풀었는데, 각각 Back Tracking과 조합을 이용하여 해결하였다.
두 풀이 방법 공통적으로 1000 이하의 모든 삼각수를 구하여 저장한다.

Back Tracking

DFS()를 이용하여 앞서 저장한 삼각 수를 하나 씩 뽑는다.
뽑은 삼각수가 1000이 넘거나, 4개 이상을 뽑으면 더 이상 가망성이 없는 것이므로 false를 리턴한다.
뽑은 삼각수의 합이 주어진 Test Case와 같으며, 3개를 뽑았다는 것은 목표와 충합하므로 true를 리턴한다.
DFS()가 끝난 후, true를 리턴하면 1, false를 리턴하면 0을 출력한다.

조합

DFS()를 이용하여 앞서 저장한 삼각 수를 3개를 뽑아, 그 합을 새로운 벡터에 저장한다.
하지만 이는 T1(1) + T2(3) + T5(15) = 19와 T2(3) + T3(6) + T4(10) = 19과 같이 중복 된 값이 나올 수 있다.
이는 Unique를 이용하여 제거 한다.
이후 Test Case를 하나씩 받으며, 이 값이 앞서 저장한 삼각수의 합 중 존재하면 1을 출력하고, 없으면 0을 출력한다.

코드 - Back Tracking

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int> trigo;      	//Trigonometric , 삼각수
bool DFS(int tc, int lv, int curl);
vector<int> result;
vector<int> trigoSum;		// 삼각수의 합
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    int sum = 1;
    trigo.push_back(1);
    while (1) {								//모든 삼각수를 구해줍니다.
        sum++;
        if (trigo.back() + sum > 1000)
            break;
        trigo.push_back(trigo.back() + sum);	//1 부터 시작하여 2,3,4,5... 등 1씩 더해준 값을 이전 삼각수에 더해 줍니다.  
    }
    int temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        result.push_back(DFS(temp, 0, 0));			//TC를 DFS에 넣어, 3개의 삼각 수의 합을 찾으면 true를 반환 후 1을 저장하고, false를 반환하면 0을 저장합니다.
    }
        
    for (int i = 0; i < result.size(); i++)
        cout << result.at(i) << "\n";
}
bool DFS(int tc, int lv, int curl) {
    if (curl > tc || lv > 3) {						//Promising 조건, 3개 초과의 삼각수를 뽑거나, 삼각수의 합이 tc 보다 클 시에 false 반환
        return false;
    }
    if (curl == tc && lv == 3) {					//성공 조건, 3개의 삼각수를 뽑아 tc와 동일한 수가 포착시 true 반환
        return true;
    }
    for (int i = 0; i < trigo.size(); i++) {
        if (DFS(tc, lv + 1, curl + trigo[i])) {		//다음 삼각수를 하나 뽑으며, 합한 값을 넘겨줍니다. 만약 true를 반환하면 DFS는 종료됩니다.
            return true;
        }
    }
    
    return false;
}

코드 - 조합

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int> trigo;      	//Trigonometric , 삼각수
void DFS(int lv, int sum);
vector<int> result;
vector<int> trigoSum;		// 삼각수의 합
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    int sum = 1;
    trigo.push_back(1);
    while (1) {
        sum++;
        if (trigo.back() + sum > 1000)
            break;
        trigo.push_back(trigo.back() + sum);
    }
    DFS(0, 0);							//삼각수 3개를 더한 1000 이하의 합
    sort(trigoSum.begin(), trigoSum.end());
    trigoSum.erase(unique(trigoSum.begin(), trigoSum.end()), trigoSum.end());	//중복 제거
    int temp;
    bool success = false;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        for (int i = 0; i < trigoSum.size(); i++) {				//TC가 삼각수의 합 중 있으면, true
            if (trigoSum.at(i) == temp) {
                success = true;
                break;
            }
        }
        if (success)
            result.push_back(1);
        else
            result.push_back(0);
        success = false;
    }
        
    for (int i = 0; i < result.size(); i++)
        cout << result.at(i) << "\n";
}
void DFS(int lv, int sum) {							//삼각수의 합을 구합니다.
    if (lv == 3) {
        trigoSum.push_back(sum);
        return;
    }
    for (int i = 0; i < trigo.size(); i++) {
        if (sum + trigo.at(i) > 1000)
            return;
        DFS(lv + 1 , sum + trigo.at(i));
    }
}

후기 및 개선할 점

문제 조건에 강조한, 단, 3개의 삼각수가 모두 달라야 할 필요는 없다를 읽지 못하여 계속하여 틀렸다.
처음에 백 트래킹으로 풀었다가 틀려 조합의 방식으로도 풀었는데, 채점의 같은 지점에서 틀렸습니다가 나와 분명 문제 조건에서 틀렸다고 생각하여 확인해보니
혹시나가 역시나라고, 중복을 배제하여 풀었는데 중복 허용이라 적혀있어 허탈하였다.
그래도 2가지의 방식으로, 또한 정답을 보지 않고 나의 힘으로 풀었다는 것에 의의를 둔다.