[Python] 25921번 건너 아는 사이

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

25921번: 건너 아는 사이

---

 

22/11/06

 

 

대회 도중에는 거의 접근을 가까이했지만 풀지 못했으나, 이후 살짝 고쳐서 맞았습니다를 받은 문제이다.

 

그래프 문제처럼 보이는 소수 판정 문제로, 참 기발하다고 생각했다.

---

 

문제 접근 방식:

 

 

음식의 가격의 합을 작게 하려면 최대한 음식을 먹는 횟수가 적어야 할 것이다.

 

다시 말해, 밥을 먹는 사람들의 번호를 노드, 서로 밥을 먹는 사람들끼리 잇는 것을 간선이라고 한다면, 우리는 이 간선의 개수를 최소한으로 만들어야 한다.

 

쉽게 이야기하자면 서로 만나서 밥 먹는 횟수가 적어야 된다.

 

따라서, 이 그래프에서는 사이클이 없어야 된다. (왜냐하면, 사이클이 있다는 것은 이미 밥을 먹은 사람하고 같이 밥을 먹는다는 뜻이기 때문에 낭비이다.)

 

그 말은 곧 트리 구조를 띠고 있다는 말이므로, 간선의 개수는 총 N-1개가 된다.

 

 

우리는 이제 그러면 그래프가 트리 구조를 띠도록 간선들을 이으면 된다.   

 

 

문제를 보면, 두 사람의 번호가 서로소가 아닐 때, 두 번호의 최대 공약수가 음식의 가격이 된다고 했다.

 

또한, 두 사람의 번호가 서로소일 때, 두 번호 중 큰 값이 음식의 가격이 된다고 했다.

 

그러면 이 규칙을 가지고, 그래프가 트리 구조를 띠면서 음식 가격이 최소가 되도록 (간선의 가중치가 최소가 되도록) 한번 구성해보자.

 

 

예를 들어, N이 10이라고 해보자.

 

1이랑 이어지는 모든 숫자는 항상 서로소이기 때문에, 두 번호 중 큰 값, 다시 말해 1이랑 이어지는 숫자가 음식의 가격이 된다.

 

따라서, 1과 이어지는 애들 중에서 1과 이어지는 간선의 가중치가 최소가 되게 하려면 1과 2가 서로 이어져야 되고, 가중치는 2가 될 것이다.

 

2는 1과 이미 이어져 있으므로 패스.

 

 

3은 소수이므로, 3의 배수나 3보다 작은 어떠한 수와 이어도 항상 3만큼의 비용이 든다.

그리고 그것이 3을 다른 숫자와 이을 때의 최소 비용이다.

 

왜냐하면, 일단 3과 서로소인 숫자를 뽑아서 3과 연결하면, max함수를 취해주기 때문에 그 간선의 가중치는 적어도 3보다는 크거나 같다. 따라서 손해이다.

 

예시를 들어보자면, 3과 4는 서로소인데, 3과 4를 이어버리면 그 간선은 가중치가 4가 나와버리게 된다.

 

서로소가 아닌 경우, 다시 말해, 어떤 숫자가 3의 배수인 경우 3과 그 숫자의 최대공약수는 항상 3이므로 3이다.

그리고 그것이 더 이득이라는 사실을 알 수 있다.

 

 

3의 예시를 통해 우리는 모든 소수들이 저 상황에 해당된다는 것을 알 수 있다.

 

다시 말하면, 모든 소수들은 어떤 숫자와 최소한의 가중치로 이었을 때, 자기 자신의 숫자에 해당하는 만큼의 가중치를 가지고 있다.

 

그 말은 모든 소수들이 사실상 1과 이어져 있다고 생각해도 무방하다는 뜻과 같다. (1과 어떤 수를 잇는 간선의 가중치는 어떤 수의 크기와 같으므로)

 

 

 

4인 경우, 4를 다른 숫자와 이으면서 그 간선의 가중치가 최소가 되게 하려면 2와 이어야 한다.(이때의 가중치는 2가 된다.)

 

먼저 4와 서로소인 친구를 4와 이으면 손해이다.

 

서로소인 경우라면 max함수를 취해주기 때문에 적어도 간선의 가중치가 4보다는 크게 나오기 때문이다.

 

따라서 4와 서로소가 아닌 친구들 중에서 4와 이어야 한다.

 

서로소가 아닌 경우에, 예를 들어 8같은 경우라면 4와 8을 이으면 가중치가 4가 되기 때문에 2와 잇는 것보다 더 크다.

따라서 서로소가 아닌 경우 중에서도 4의 배수 같은 것들은 이으면 안 된다.

 

최대 공약수가 커져서 가중치가 더 커지기 때문이다.

 

 

 

이 경우를 통해서 추측을 하자면, 2의 배수들(4, 6, 8...)들은 2와 잇는 것이 항상 최소이다.

 

2의 배수들의 만약 다른 서로소인 숫자와 이어버리면 max함수를 취해줘서 적어도 그 숫자보다는 큰 간선의 가중치가 나와서 노이득이여서 2의 배수이면서 서로소로 이어버리면 안 된다.

 

따라서 같은 2의 배수끼리(서로소가 나오게) 잇는 것이 최선이다.

근데, 아까 전 예시의 4와 8처럼 뽑으면 최대 공약수가 더 크게 나올 수 있다.

 

따라서 최대공약수를 최소화시키려면 그냥 제일 작은 2와 연결하는 것이 간선의 가중치를 최소화하는 방법이다.

 

 

 

이를 일반화시키면, 소수의 배수들은, 그 소수와 잇는 것이 더욱 낫다.

 

빨간색으로 쓴 문장 2개를 통해서, 우리는 그래프가 트리 구조를 띠게 되었다는 사실을 알 수 있다.

 

우리가 N=10으로 예시를 들었는데, 1은 2, 3, 5, 7과, 2는 4, 6, 8, 10과, 3은 9와 잇게 되면 트리가 만들어진다.

 

 

 

이를 잘 생각해보자.

 

그러면 이는 우리가 결국 소수만 판별하면 되는 것이고, 소수의 배수들은 소수만큼의 가중치를 가지므로, 에라토스테네스의 체를 돌릴 때, 약간의 변형만 하면 될 것이라는 것을 쉽게 유추해낼 수 있다.

 

이를 이용하여 문제를 해결하면 끝이다.

 

그래프 이론이 조금 섞이긴 했지만, 구현과 핵심 아이디어 자체는 소수와 최대 공약수 부분에 달려있었으므로, 사실상 소수 판별 문제라고 볼 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 25921번 건너 아는 사이
# 에테체, 소수 판정
import sys
input = sys.stdin.readline

arr = [0 for _ in range(1000001)]
arr[1] = 0
N = int(input())
total = 0
for i in range(2, N+1):
    if arr[i] == 0:
        arr[i] = 1
        total += i
        for j in range(2*i, N+1, i):
            if arr[j] == 0:
                arr[j] = 1
                total += i

print(total)