백준 17610번 양팔저울 [C++]

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

 

 

#문제 간단 정리

 

#문제 해결 방법

 

생각보다 무게를 만들수 있는 가짓수가 많지 않기때문에

 

우선 그릇 하나만 써서 만들수 있는 무게를 모두 만든다.

 

그 이후에 만든 무게중에 두개를 빼서 만들수 있는 무게를 확인한다.

이 모든 만든 무게들을 출력해주면 된다.

 

나는 무게 만드는데는 dfs를 사용했다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>


using namespace std;

vector<int> mess;
vector<int> makes;
vector<bool> check;
vector<bool> dfsCheck;
vector<int> messNext;

//한곳에 만들수 있는 모든 무게추 구하기
void dfs(int index,int sumMess) {

    for (int i = 0; i < mess.size(); i++) {
        if (dfsCheck[i] == false) {
            dfsCheck[i] = true;
            if (check[sumMess + mess[i]] == false) {
                check[sumMess + mess[i]] = true;
                messNext.push_back(sumMess + mess[i]);
                dfs(i,sumMess + mess[i]);
            }
            dfsCheck[i] = false;
        }
    }

}


int main()
{
    int k;
    cin >> k;
    int s = 0;
    mess.resize(k);
    check.resize(3000'001, false);
    dfsCheck.resize(3000'001, false);

    for (int i = 0; i < k; i++) {
        cin >> mess[i];
        s += mess[i];
        //cout << "s: " << s << '\n';
        messNext.push_back(mess[i]);
        check[mess[i]] = true;
    }

    for (int i = 0; i<mess.size(); i++) {
        dfsCheck[i] = true;
        dfs(i, mess[i]);

    }

    //두개 골라서 빼기
    for (int i = 0; i < messNext.size()-1; i++) {
        for (int j = i + 1; j < messNext.size(); j++) {
            if (check[abs(messNext[i] - messNext[j])] == false) {
                check[abs(messNext[i] - messNext[j])] = true;
            }
        }

    }

    ////무게확인
    //for (int i = 0; i <= s; i++) {
    //    if (check[i] == true) {
    //        cout << i << " ";
    //    }
    //}

    //안 만들어진 무게추 확인
    int count = 0;
    //cout << "count: ";
    for (int i = 1; i <= s; i++) {
        if (check[i] == false) {
            count++;
        }
    }
    cout << count << '\n';

}