[C] 백준 - 17103번: 골드바흐 파티션

5월 4일(목) - 약수, 소수와 배수 2 (17103번)

17103번: 골드바흐 파티션

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이전에 풀이했었던 9020번: 골드바흐의 추측 문제에서의 내용을 활용해야할 것 같다

8월 14일(일) - 8단계(9020번 *실패->성공)

- 입력은 test_case와 그에 따라서 입력되는 짝수들 -> 짝수들은 변수 num으로 입력받음

- 배열 arr[ i ]에다가 자신의 i 값을 넣어놓은뒤, 소수가 아닌 값들의 배열값은 0으로 바꾼다

- 골드바흐 파티션의 개수를 변수 answer에 하나씩 추가해야한다

  소수 + 소수를 해서 num이 되는 경우에 answer++

- 하지만 똑같은 소수를 더해서 num이 되는 경우도 존재

   ex) 10 = 5 + 5

- 따라서 해당 경우를 추가적으로 answer++ 해준다

- 최종적으로 answer / 2 를 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include<stdio.h>
int arr[1000001];

int main(void)
{
	for (int i = 2; i < 1000001; i++)
	{
		arr[i] = i;
	}

	for (int i = 2; i <= 1000001; i++)
	{
		for (int j = 2; j * i <= 1000001; j++)
		{
			arr[i * j] = 0;
		}
	}

	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++)
	{
		int num;
		int answer = 0;
		scanf("%d", &num);

		for (int i = 2; i < num; i++)
		{
			if (arr[i] + arr[num - i] == num)
			{
				answer++;

				if (num - i == i)
				{
					answer++;
				}
			}

		}

		printf("%d\n", answer / 2);
	}
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ