2장 p30 사탕 나눠주기

#include <iostream>

#include <random>

#include <queue>

using namespace std;

int color[220][220][220];

int arr[30];

const int C = 30;

int sum;

class node{

public:

int arr[3];

int index;

node(int a, int b, int  c, int d){arr[0] = a; arr[1]=b;arr[2]=c;index=d;}

bool operator<(node right) const

{

int lv = arr[0] - arr[2];

int rv = right.arr[0] - right.arr[2];

if(lv > rv) return true;

else return false;

}

};

//bfs

void seek()

{

queue<node> q;

q.push(node(0,0,0,0));

while(!q.empty())

{

node now = q.front();

q.pop();

if(now.index == C)

{

cout<<now.arr[0]<<" "<<now.arr[1]<<" "<<now.arr[2]<<" "<<endl;

break;

}

node temp = now;

temp.index++;

int *v = temp.arr;

for(int i=0; i<3; i++)

{

v[i] += arr[now.index];

//오름차순 정렬 및 이미 방문한 곳 방문 안함

if(v[0] >= v[1] && v[1] >=v[2] &&  color[v[0]][v[1]][v[2]] == 0)

{

//최대 최소 차이가 20이 넘는 경우 배제

if(v[0]-(sum - v[0] - v[1])  <= 20)

{

color[v[0]][v[1]][v[2]] = 1;

q.push(temp);

}

}

v[i] -= arr[now.index];

}

}

}

int main()

{

for(int i=0; i<C; i++)

{

arr[i] = rand()%20+1;

cout<<arr[i]<<" ";

sum+=arr[i];

}

sort(&arr[0],&arr[30], greater<int>());

cout<<endl<<endl;

seek();

}