[백준/2548] 대표 자연수 (Python)

Problem : 2548번: 대표 자연수 (acmicpc.net)

2548번: 대표 자연수

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:14:11

 

 

---

 

문제 설명

 

정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다.

“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”

예를 들어 주어진 자연수들이 [4, 3, 2, 2, 9, 10]이라 하자. 이때 대표 자연수는 3 혹은 4가 된다. 왜냐하면 (4와 3의 차이) + (3과 3의 차이) + (2와 3의 차이) + (2와 3의 차이) + (9와 3의 차이) + (10과 3의 차이) = 1+0+1+1+6+7 = 16이고, (4와 4의 차이) + (3과 4의 차이) + (2와 4의 차이) + (2와 4의 차이) + (9와 4의 차이) + (10과 4의 차이) = 0+1+2+2+5+6 = 16으로 같으며, 이 두 경우가 차이들의 합을 최소로 하기 때문이다. 비교를 위하여 평균값인 5의 경우를 생각하여 보면, (4와 5의 차이) + (3과 5의 차이) + (2와 5의 차이) + (2와 5의 차이) + (9와 5의 차이) + (10과 5의 차이) = 1+2+3+3+4+5 = 18로 위의 두 경우보다 차이들의 합이 더 커짐을 볼 수 있다.

연아를 도와서 위의 성질을 만족하는 대표 자연수를 구하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다.

 

출력

첫째 줄에 대표 자연수를 출력한다. 대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.

 

입력 예시

6
4 3 2 2 9 10

 

출력 예시

3

 

 

---

 

풀이

 

브루트포스로 풀되, 접근법에 대해 잘 생각해 보아야 한다. 우선 '대표 자연수'가 주어진 리스트에 존재한다고 가정하자. 리스트의 모든 수를 하나씩 그 차를 비교해보는 방법은 시간복잡도가 O(N^2)이 되며, N은 최대 20,000까지이므로 이는 당연히 시간 초과를 불러일으키게 된다.

리스트를 정렬한 후 막대그래프 형태로 생각해 보자.

제일 왼쪽을 대표 자연수(=2)라고 가정하면, 차이들의 총합은 빨간 직사각형 안에 있는 사각형의 개수, 즉 18이다.이제 두 번째로 낮은 막대, 즉 3을 대표 자연수로 가정해보자.

 

이 경우 차의 총합은 초록색 직사각형과 빨간색 직사각형 안의 차이를 나타내는 직사각형의 개수. 즉 16이다. 초록색 직사각형이 생성되고, 그에 맞추어 빨간색 직사각형의 면적이 줄어들었다. 감이 오지 않는가? 리스트의 모든 수에 대하여, 초록색 직사각형의 늘어나고, 빨간색 직사각형의 면적은 줄어든다. 그리고 차이의 총합은 이에 따라 변동하게 된다.

 

 

구체적으로, 리스트 안의 이전 자연수와 현재 자연수의 차이를 '높이'라고 가정할 때, 초록색 직사각형 내 차이 합은 (높이 * 현재 인덱스)만큼 늘어나고, 빨간색 직사각형 내 차이 합은 높이 * (최대 인덱스 - 현재 인덱스) 만큼 줄어든다. 즉 N번의 단 한 번의 순회 동안, 이러한 방식으로 모든 높이 차이 합에 대해 비교할 수 있다. 이런 식의 정렬 후 비교 문제는 기본적으로 자주 나오니 개념을 이해하고 넘어가는 게 좋다.

 

 

풀이 코드

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

left_sum, right_sum = 0, sum(num_list) - num_list[0]*N
answer, answer_sum = 0, right_sum
for i in range(1, N) :
  height = num_list[i] - num_list[i-1]
  left_sum += height*i
  right_sum -= height*(N-i)

  if left_sum + right_sum < answer_sum :
    answer = i
    answer_sum = left_sum + right_sum

print(num_list[answer])

풀이 완료~