25921 건너 아는 사이

25921 건너 아는 사이 (c++)

문제

https://www.acmicpc.net/problem/25921

접근 방식

소수

음식 값의 두 가지 조건이 있다.

1. 두 사람의 번호가 서로소일 때, 두 번호 중 큰 값
2. 두 사람의 번호가 서로소가 아닐 때, 두 번호의 최대 공약수

이 때 음식 값이 최소가 되려면

1. 서로소는 어쩔 수 없이 큰 값을 더한다.
2. 최대 공약수가 가장 작은 값을 찾는다. (즉 2로 나누어지는 수는 전부 2와 연결한다.)

이를 다시 말하면 2부터 N까지 수를 돌면서 에라토스테네스의 체를 돌리며, 아직 체크하지 않은 값을 더한다는 말과 같다. (만약 소수가 아니라면 나눠지는 값을 더하고)

문제 풀이

#include <iostream>
using namespace std;

bool arr[1'000'001] = {};

int main()
{
	int N;
	cin >> N;

	unsigned long long answer = 0;

	for (int i = 2; i <= N; ++i)
	{
		if (arr[i]) continue;
		for (int j = i; j <= N; j += i)
		{
			if (arr[j]) continue;
			arr[j] = true;
			answer += i;
		}
	}

	cout << answer << endl;

	return 0;
}

다시 생각해 볼 점

1. 서로 연결되야 한다는 조건은 복잡해 보일 수 있지만 결국 모든 소수는 1과 연결되고, 모든 합성수는 소수와 연결되기 때문에 결국 에라토스테네스의 체와 같다.
2. 한번에 맞출 수 있는 문제였는데, 처음에 음식 값의 합을 나타내는 answer 변수를 int로 선언했다가 오버플로우가 나서 틀렸다. 항상 최소값과 최대값을 넣어보자.