JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

1. 랜선 자르기

  • 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다.

  • 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

  • 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다.
  • 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.

  • 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

  • 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.
  • 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자.
  • N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
  • 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다.

    • K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다.
    • 그리고 항상 K ≦ N 이다.

  • 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다.

    • 랜선의 길이는 $2^{31}-1$보다 작거나 같은 자연수이다.

출력

  • 첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이

def div_find(left,right,lan,N):
    mid = (left + right) // 2 if (left+right)//2 != 0 else 1

    arr = sum([x // mid for x in lan])
    arr2 = sum([x // (mid + 1) for x in lan])

    if left > right:
        return mid

    if arr == N:
        if N > arr2:
            return mid
        else:
            return div_find(mid+1,right,lan,N)
    elif arr > N:
        return div_find(mid + 1,right,lan,N)
    elif arr < N:
        return div_find(left,mid - 1,lan,N)

import sys

K, N = list(map(int, sys.stdin.readline().split()))

lan = []

for _ in range(0, K):
    lan.append(int(sys.stdin.readline()))

print(div_find(0,max(lan),lan,N))

채점 결과

  • 정답

리뷰

  • 이분 탐색을 응용하여 풀어야 하는 문제였다.

  • mid 값으로 각 랜선을 나눈 값들의 총합을 비교하며 mid에 대해 이분탐색을 진행한다.

  • 이때, mid + 1로 나누었을 경우 N개보다 적게 나오는 경우(즉, mid로 나누었을때 N이 나올수 있는 최대값일때) mid를 반환한다.

    • 최대값이 아닌 경우는 left값을 올려 재탐색을 진행한다.

더 나은 풀이

from sys import stdin
K, N = map(int,stdin.readline().split())
li = list(map(int,stdin.readlines()))
h, l = sum(li)//N, 1
while l <= h :
    mid = (h+l)//2
    cnt = sum([x//mid for x in li])
    if cnt < N:
        h = mid - 1
    elif cnt >= N:
        l = mid + 1
        ans = mid
print(ans)

더 나은 풀이 리뷰

  • 최대값은 총 랜선 길이의 N등분으로, 최솟값은 1로 설정했다.

  • 그 뒤에는 이분탐색을 진행하는것은 동일했다.

2. 통계학

  • 수를 처리하는 것은 통계학에서 상당히 중요한 일이다.
  • 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다.

  • 단, N은 홀수라고 가정하자.

    1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
    2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
    3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
    4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이
  • N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
    • 단, N은 홀수이다.
  • 그 다음 N개의 줄에는 정수들이 주어진다.
    • 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

  • 첫째 줄에는 산술평균을 출력한다.
    • 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

  • 둘째 줄에는 중앙값을 출력한다.

  • 셋째 줄에는 최빈값을 출력한다.
    • 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
  • 넷째 줄에는 범위를 출력한다.

풀이

import sys

N = int(sys.stdin.readline())
arr = [None] * 8001
idx = 4000

for _ in range(0,N):
    k = int(sys.stdin.readline())
    if arr[idx+k]:
        arr[idx+k] += 1
    else:
        arr[idx+k] = 1

unzip = [[x-idx] * arr[x] for x in range(0,len(arr)) if arr[x]]
arr_unzip = []
for x in unzip:
    arr_unzip += x

print(round(sum(arr_unzip)/len(arr_unzip)))
print(arr_unzip[len(arr_unzip)//2])

freq_arr = [x for x in unzip if len(x) == max([len(x) for x in unzip])]

print(freq_arr[1][0] if len(freq_arr) > 1 else freq_arr[0][0])
print(arr_unzip[-1] - arr_unzip[0])

채점 결과

  • 정답

리뷰

  • 입력값의 갯수가 엄청나게 많지만 입력되는 수의 크기가 이상하게 작게 설정되어있는 부분에서 인덱스를 통한 유사 딕셔너리를 활용해야 함을 직감적으로 알아차렸다.

  • [None]으로 초기화한 8001 크기의 리스트를 설정하고, 기준 idx를 4000으로 잡아 음수값은 0~3999번, 양수값은 4001~8000번까지의 인덱스에 갯수를 추가하는 방식으로 진행했다.

  • unzip 리스트를 통해 각 숫자를 나온 갯수만큼 출력하며 자연스럽게 정렬한다.

  • arr_unzip을 통해 정렬된 리스트를 출력하며 동시에 산술평균을 구한다.

  • 중앙값은 arr_unzip의 len(arr_unzip)//2번째 인덱스의 값이므로, 출력한다.

  • freq_arr로 가장 많이 나온 숫자의 갯수와 그 숫자를 출력한다.

  • 최빈값은 freq_arr이 1개 이상일때는 두번째로 작은 값을 출력, 1개일때는 해당 값을 출력한다.

  • 범위는 arr_unzip의 가장 큰 값(-1번째 인덱스 값)에서 가장 작은 값(0번째 인덱스)를 뺀 값이다.

You May Also Enjoy