그리디 알고리즘(3)

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

18310번: 안테나

 

그리디는 작게 쪼개서 최선의 선택을 하면 그게 최적의 해가 된다는 발상인데,,,,,,, 풀다보면 와닿지가 않네

문제

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자.

 

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로, 최소가 된다.

입력

첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

출력

첫째 줄에 안테나를 설치할 위치의 값을 출력한다. 단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.

 

 

N = int(input())
house = list(map(int,input().split()))
house.sort()
# 1 이면 1 15면 1혹은5 157이면 최대한 평균에 가까운 값??
ideal = sum(house)/len(house)
ideal_house = float("inf")
min_value = float("inf")
for i in range(N):
  if min_value>abs(ideal-house[i]):
    min_value = abs(ideal-house[i])
    ideal_house = house[i]

print(ideal_house)

 

중앙값을 구해야하는문제에서 평균값으로 구했다. 음,, 대략적인 직관으로 중앙값?평균값?을 구하면 될거같았는데 중복수가 있을수있다는 조건에 평균값이 적절한줄..

평균값 구하는 코드:

def find_closest_to_average_index(lst):
    # 평균값 계산
    avg = sum(lst) / len(lst)

    # 평균과의 차이를 계산하고, 최소 차이를 가지는 인덱스 찾기
    min_diff = float('inf')
    closest_index = -1
    for i, value in enumerate(lst):
        diff = abs(value - avg)
        if diff < min_diff:
            min_diff = diff
            closest_index = i

    return closest_index

# 예시 리스트
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# 가장 평균에 가까운 값의 인덱스 찾기
index = find_closest_to_average_index(lst)
print(f"The index of the element closest to the average is: {index}")

뭐 이거야.. 나랑 별다를거 없고

 

쇼킹한건 중앙값 구하는 코드

N = int(input())
house = list(map(int, input().split()))
house.sort()

# 중앙값을 찾아 출력합니다.
# 짝수 개일 경우 두 중앙값 중 작은 값을 선택합니다.
median_index = (N - 1) // 2
print(house[median_index])

 

이렇게 심플하다니

중앙값이 최적의 해인 이유

1. 거리의 합 최소화: 이 문제의 목적은 모든 집까지의 총 거리의 합을 최소화하는 것입니다. 즉, 모든 집들과 안테나 사이의 거리의 합이 최소가 되어야 합니다.
2. 균형점 찾기: 집들이 일렬로 늘어선 상태에서, 중앙에 위치한 집은 양쪽에 위치한 집들까지의 거리 합이 균등하게 분포되도록 합니다. 이는 안테나를 중앙에 두었을 때, 한 쪽에 치우치지 않고 양쪽 집들까지의 거리가 균형을 이루게 만듭니다.
3. 극단값 문제 해결: 안테나를 중앙이 아닌 다른 위치에 설치한다고 가정해 봅시다. 이 경우 안테나가 한쪽 끝으로 갈수록, 그 반대편 끝에 있는 집까지의 거리는 급격하게 증가합니다. 결과적으로 거리의 합이 더 커지게 됩니다.
4. 수학적 증명: 각 집의 위치를 x1, x2, ..., xn이라고 할 때, 안테나 위치를 a라고 합니다. 이때, 거리의 합 S = |x1 - a| + |x2 - a| + ... + |xn - a|를 최소화하는 a의 값은 중앙값입니다. 이는 미적분학에서의 중간값 정리(Mean Value Theorem)를 통해 증명할 수 있습니다.

짝수일 때 더 작은 값 선택 이유

1. 두 중앙값: 집의 수가 짝수일 때, 중앙에는 두 개의 값이 위치합니다. 이 두 값 사이 어디에 안테나를 설치해도 거리 합의 변화는 없습니다. 왜냐하면 한쪽으로 한 단계 이동할 때마다 한쪽 집에서는 1 증가하지만, 반대편 집에서는 1 감소하기 때문입니다.
2. 최소값 선택 기준: 문제의 요구 사항에 따라, 가능한 안테나 위치가 여러 개일 경우 가장 작은 값을 선택해야 합니다. 이는 문제의 특정 요구 사항으로, 수학적인 최적화와는 별개의 조건입니다.

결론

따라서 중앙값을 선택하는 것은 이 문제에서 모든 집까지의 거리 합을 최소화하는 가장 효율적인 방법입니다. 홀수 개의 집이 있을 때는 명백한 중앙값을, 짝수 개의 집이 있을 때는 두 중앙값 중 더 작은 값을 선택하는 것이 문제의 요구 사항에 부합합니다.

 

어쨌든 그리디는 좀 센스가 필요한거같다