백준 14697 방배정하기

#include <cstdio>

using namespace std;

int main()

{

int A, B, C, N;

int i = 1, j = 1, k = 1; // N의 값보다 작은 A, B, C의 배수를 arr배열에 저장하기 위함. 

bool existA = false, existB = false, existC = false; //arr 배열에 N보다 작은 A, B, C 배수를 저장을 완료하면 탈출하기 위함

int arrA[301] = { 0, }, arrB[301] = { 0, }, arrC[301] = { 0, };

scanf("%d %d %d %d", &A, &B, &C, &N);

// 각 arr배열에 N보다 작은 A, B, C의 배수 저장

while(true){

if (arrA[i - 1] + A <= N){

arrA[i] = arrA[i - 1] + A;

i++; 

}

else

existA = true;

if (arrB[j - 1] + B <= N){

arrB[j] = arrB[j - 1] + B;

j++;

}

else

existB = true;

if (arrC[k - 1] + C <= N){

arrC[k] = arrC[k - 1] + C;

k++; 

}

else

existC = true;

if (existA == true && existB == true && existC == true)

break;

}

/*

i, j, k 3중 반복문으로 계산. 도중에 합계가 초과되면 백트래킹으로 가지치기를 한다.

*/

bool checkExistAns = false;

for (int ii = 0; ii < i; ii++){

int sum = 0;

sum += arrA[ii];

for (int jj = 0; jj < j; jj++){

sum += arrB[jj];

for (int kk = 0; kk < k; kk++){

sum += arrC[kk];

if (sum == N){

//종료

checkExistAns = true;

break;

}

else if (sum > N){

sum -= arrC[kk];

break;

}

sum -= arrC[kk];

}

//답이 존재하면 탈출

if (checkExistAns == true) break;

sum -= arrB[jj];

}

//답이 존재하면 탈출

if (checkExistAns == true) break;

}

//정답이 있을 경우와 없을 경우 답 출력

if (checkExistAns == true){

printf("1\n");

}

else{

printf("0\n");

}

return 0;

}