왜 오답이 나오는지 모르겠습니다.
20000까지 weird num만 출력되도록 테스트 해봤을때도
문제없이 잘 나오는거 같은데...
도와주세요!
코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 250000
int divisors[MAX] = { 0 };
int *sub_divisors;
int sub_max_idx = 0;
int diff = 0 ;
int sub_sum = 0;
enum RESULT { FALSE, TRUE };
int getDivisors(int num);
int verify(int num);
int equalNum(int* subArrayt);
int getDivisors(int num)
{
int i, j;
for (i = 1, j = 0; i <= num / 2; i++)
{
if (num%i == 0)
{
divisors[j] = i;
j++;
}
}
return j;
}
int verify(int num)
{
int sum = 0;
int i = 0, max_idx = 0;
int ret;
max_idx = getDivisors(num);
// Condition 1. num 초과
for (i = 0; i < max_idx; i++)
{
sum += divisors[i];
}
if (sum <= num) return FALSE;
// Condition 2. no subset such that sum of subset = num
diff = sum - num;
for (sub_max_idx = 0; sub_max_idx < max_idx; sub_max_idx++)
if (divisors[sub_max_idx] > diff) break;
sub_divisors = (int *)malloc(sizeof(int)*sub_max_idx);
for (i = 0; i < sub_max_idx; i++)
sub_divisors[i] = divisors[sub_max_idx - i - 1];
ret = equalNum(sub_divisors);
free(sub_divisors);
sub_sum = 0;
return ret;
}
int equalNum(int* subArray)
{
int pivot = 0;
int i = 0;
for (pivot = 0; pivot < sub_max_idx; pivot++)
{
sub_sum += subArray[pivot];
if (sub_sum == diff) return FALSE;
for (i = pivot + 1; i < sub_max_idx; i++)
{
sub_sum += subArray[i];
if (sub_sum == diff) return FALSE;
else if (sub_sum > diff)
{
sub_sum -= subArray[i];
}
}
sub_sum -= subArray[pivot];
}
return TRUE;
}
int main()
{
int num;
int condition;
int testcase;
scanf("%d", &testcase);
while (testcase--)
{
memset(divisors, 0, sizeof(int)*MAX);
scanf("%d", &num);
condition = verify(num);
if (condition == TRUE) printf("weird\n");
else if (condition == FALSE) printf("not weird\n");
}
return 0;
}
10년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
ghlee0228
왜 오답이 나오는지 모르겠습니다.
20000까지 weird num만 출력되도록 테스트 해봤을때도
문제없이 잘 나오는거 같은데...
도와주세요!
코드
10년 전