제 생각에는 부분합을 구하는 부분에서 오래 걸리는 거 같아 시간 초과가 나오는 것 같습니다. 그런데 합계가 있어서 동적프로그래밍을 사용하는 것도 무리이고 어떻게 하면 최적화를 할 수 있을까요?
~~~c++
int subset(int* mem, int number, int index, int sum) { // 부분집합의 합 중 number와 같은 게 있으면 1, 없으면 0
if (sum == number)
return 1;
if (index >= memCnt || sum > number)
return 0;
if (index != -1)
sum += mem[index];
printf("sum : %d\n", sum);
return subset(mem, number, index+1,sum) || subset(mem, number, index+2,sum);
}
~~~
8년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
go1217jo
제 생각에는 부분합을 구하는 부분에서 오래 걸리는 거 같아 시간 초과가 나오는 것 같습니다. 그런데 합계가 있어서 동적프로그래밍을 사용하는 것도 무리이고 어떻게 하면 최적화를 할 수 있을까요?
~~~c++
int subset(int* mem, int number, int index, int sum) { // 부분집합의 합 중 number와 같은 게 있으면 1, 없으면 0
if (sum == number)
return 1;
if (index >= memCnt || sum > number)
return 0;
if (index != -1)
sum += mem[index];
printf("sum : %d\n", sum);
return subset(mem, number, index+1,sum) || subset(mem, number, index+2,sum);
}
~~~
8년 전