ACM-ICPC 대전 2014 C번

알고리즘 문제 ACM-ICPC 대전 2014 C번

심심할때 알고리즘이나 풀고자한다. 안 심심해지기는 하는데 스트레스받는다 잘 안풀려서

문제링크: https://www.acmicpc.net/problem/10448

소스코드

직접 짠 코드라 매우 개판이다ㅋㅋ icpc문제의 진짜 재미는 풀기성공하고 다른 사람소스보며 감탄하는 재미에 있다...ㅠㅠ

#pragma warning (disable:4996)

#include <stdio.h>

#include <stdlib.h>

#define SIZE 46

int eureka(int natural);

int eureka_last(int natural);

int Tn[SIZE] = { 0 }; //삼각수

int main(void)

{

int T;

int test_case;

int *answer;

int i;

scanf("%d", &T); // 첫 번째 줄에 테스트케이스의 개수 T가 주어진다.

answer = (int *)malloc(sizeof(int)*T);

Tn[0] = 1;

for (i = 1; i < SIZE; i++)

Tn[i] = i*(i + 1) / 2;

for (test_case = 0; test_case < T; test_case++) // 로직

{

int i=0; //카운트변수

int K[4] = { 0 }; //사용자 입력값

int count[3] = { 0 }; //eureka에 횟수 전달용

int K1_index, K2_index, K3_index;

scanf("%d", &K[0]); //각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함

//printf("K[0] = %d\n", K[0]);

for (K1_index = eureka(K[0]); K1_index > 0; K1_index--)

{

K[1] = Tn[K1_index];

//printf("K[1] = %d\n", K[1]);

if (K[1] <= K[2])

break;

for (K2_index = eureka(K[0] - K[1]); K2_index > 0; K2_index--)

{

K[2] = Tn[K2_index];

//printf("K[2] = %d\n", K[2]);

if (K[2] <= K[3])

break;

K3_index = eureka_last(K[0] - K[1] - K[2]);

K[3] = Tn[K3_index];

//printf("K[3] = %d\n", K[3]);

if (K[1] + K[2] + K[3] == K[0])

break;

}

if (K[1] + K[2] + K[3] == K[0])

break;

}

if (K[1] + K[2] + K[3] == K[0])

answer[test_case] = 1;

else

answer[test_case] = 0;

}

for (test_case = 0; test_case < T; test_case++) // 출력

{

printf("%d\n", answer[test_case]);

}

free(answer); // 메모리 반납

return 0;

}

int eureka(int natural)

{

int i;

int index;

for (i = 1; i < SIZE; i++)

{

if (natural > Tn[i]) //Tn보다 K가 더 크면 계속 반복

continue;

else //Tn가 더 크자마자 반복중단

{

index = i - 1;

break;

}

}

return index;

}

int eureka_last(int natural)

{

int i;

int index;

for (i = 1; i < SIZE; i++)

{

if (natural >= Tn[i]) //Tn보다 K가 더 크면 계속 반복

continue;

else //Tn가 더 크자마자 반복중단

{

index = i - 1;

break;

}

}

return index;

}