5986번 새샘이와 세 소수

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWaJ3q8qV-4DFAUQ&categoryId=AWaJ3q8qV-4DFAUQ&categoryType=CODE

해결방법 :

문제 지문이 짧고 난이도가 d3라 쉬울 것같았지만 쉽게 풀리지 않았던 문제였다.

아름답게 풀기위해 어떤 규칙성과 어떤 로직으로 짤지 고민을 하다가 시간이 많이 지체되서 그냥 무식하게 풀자는 생각을 했다 ㅋㅋ;

나의 아이디어는 다음과같다.

1. 1차원 배열 table에 소수를 미리 체킹해둔다.

2. n = a+b+c 이므로 a,b를 2중 for문 돌리면서 각 숫자가 소수인지 아닌지를 미리 기록해둔 table을 보면서 확인했다. (c는 a,b 정해지면 자동적으로 구하니 for문 안돌림)

3. 여기서 중복된 경우는 제외해줘야 하므로 visit 2차원배열을 만들어서 a,b,c의 중복된 경우를 제외해주었다. (testcase 결과값보면 중복된걸 제외해주었음)

소스코드)

#include<stdio.h>
#include<cstring>
#define MAX 999
int table[1000]; // 소수확인정보
int visit[1001][1001];
int main()
{
    int test_case;
    int tmp;
    table[MAX] = 1; // 1은 소수 아닌것
    for (int i = 2; i <= 499; i++)
    {
        tmp = 2;
        while (i*tmp <= MAX)
        {
            table[i*tmp] = 1;
            tmp++;
        }
    } // 소수체킹 완료
    scanf("%d", &test_case);
    for (int t = 1; t <= test_case; t++)
    {
        int ret = 0;
        int N;
        
        scanf("%d", &N);
        for (int a = 2; a <= N - 4; a++)
        {
            for (int b = 2; b <= N - a - 2; b++)
            {
                int c = N - a - b;
                if (!table[a] && !table[b] && !table[c] && !visit[a][b] && !visit[a][c])
                {
                    ret++;
                    visit[a][b] = visit[b][a] = 1;
                    visit[a][c] = visit[c][a] = 1;
                }
            }
        }
        memset(visit, 0, sizeof(visit));
        printf("#%d %d\n",t, ret);
    }
}