[백준][그리디] 휴먼 파이프라인

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

22981번: 휴먼 파이프라인

 

내가 작성한 코드

import sys, math
read = sys.stdin.readline

N, K = map(int, read().rstrip().split())
nums = sorted(map(int, read().rstrip().split()))
mn = sys.maxsize
for i in range(1, N):
    x = math.ceil(K / ((nums[0] * i) + (nums[i] * (N-i))))
    if (x * (nums[0] * i)) + (x * (nums[i] * (N-i))) < K:
        x += 1
    elif ((x-1) * (nums[0] * i)) + ((x-1) * (nums[i] * (N-i))) > K:
        x -= 1
    mn = min(x, mn)

print(mn)

• 두 팀으로 나누기
  
  • 정렬시 가장 왼쪽 값이 최소값
  • 최소값 * 팀원 수이므로
    - for i in range(1, N):
    - team1 = nums[0] * i
    - team2 = nums[i] * (N-i)
  • K개의 상자를 옮겨야하므로, K / (team1+team2)의 최소값을 출력하면 됨
  • 그런데, 자꾸 85%에서 실패함
    - 정확히 어떤 케이스인지 모르겠지만, K의 최대값이 10 ** 18인 것이 소수점에 정확도 문제를 야기시킬 것 같음
    - double형의 정확도도 15자리수까지이기 때문
    - 그래서 도출된 값의 오차를 확인하는 코드를 삽입 후 통과

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 로직 잘못인가 고민을 오래한 문제
  
  • python이 특히 타입을 명시하지 않아 더 간과하게 되는 것 같다
  • 로직을 몇번이고 검토하는 것도 숙련도가 낮아서 자신이 없는 것 같다