본문 바로가기

알고리즘

모두의 연봉 1억

New Era · 11번Lv. 3이분 탐색

모두의 연봉 1억

문제 설명

대리인 No.1의 기록 중에서

라이캣이 알고리즘 7원석을 찾아 떠난 뒤, (주)캣네생선의 대표가 된 대리인 No.1은 회사를 위니브 월드 시가총액 1위로 키웠습니다. 그런데 어느 날 No.1은 회의실에서 이렇게 묻습니다.

"성장만이 우리의 목표일까냥? 직원들이 월급을 받아 집은 언제 살 수 있을까냥?"

대리인들은 목표를 정했습니다. T년 안에 모든 직원의 연봉을 1억 노드 이상으로 만들기. 회사 재정도 생각해야 하므로, 모든 직원에게 같은 연간 상승률 r%(0 이상의 정수)를 적용하되 r은 되도록 작게 잡으려고 합니다.

연봉은 1년이 지날 때마다 아래 규칙으로 오릅니다(복리).

  • 새 연봉 = 지금 연봉 + (지금 연봉 × r ÷ 100에서 소수점 아래를 버린 값)
  • 예를 들어 연봉 52,000,000노드에 r = 14이면, 1년 뒤 연봉은 52,000,000 + 7,280,000 = 59,280,000노드입니다.
  • 연봉 1,234,567노드에 r = 3이면, 1,234,567 × 3 ÷ 100 = 37,037.01이므로 37,037만 더해 1,271,604노드가 됩니다.

직원들의 지금 연봉 목록과 T가 주어질 때, T번 오른 뒤 모든 직원의 연봉이 100,000,000노드 이상이 되게 하는 가장 작은 정수 r을 반환하는 solution 함수를 작성해 주세요. 이미 모든 직원의 연봉이 1억 노드 이상이면 0을 반환합니다.


제한 사항

  • data는 [연봉 목록, T] 형태입니다.
  • 1 ≤ 직원 수(연봉 목록의 길이) ≤ 10,000
  • 10,000 ≤ 각 직원의 지금 연봉 ≤ 200,000,000 (정수, 단위 노드)
  • 1 ≤ T ≤ 30
  • 위 범위에서 답은 항상 1,000,000 이하입니다.
  • r이 크면 연봉이 매우 커질 수 있습니다. 연봉이 1억 노드 이상이 된 직원은 그 뒤로도 1억 노드 아래로 내려가지 않으므로, 더 계산하지 않아도 됩니다.

입출력 예

입력출력
[[60000000, 75000000, 52000000], 5]14
[[99999999, 100000000, 120000000], 3]1
[[30000000, 8000000], 10]29

입출력 설명

입출력 예 #1

  • 연봉이 가장 적은 직원(52,000,000노드)을 r = 14로 계산하면 59,280,000 → 67,579,200 → 77,040,288 → 87,825,928 → 100,121,557이 되어 5년 뒤 1억을 넘습니다. 나머지 두 직원은 더 일찍 1억을 넘습니다.
  • r = 13이면 이 직원은 5년 뒤 95,806,628노드라 1억에 닿지 못합니다. 따라서 답은 14입니다.

입출력 예 #2

  • r = 0이면 연봉이 그대로라 99,999,999노드인 직원이 1억에 닿지 못합니다.
  • r = 1이면 1년 뒤 99,999,999 + 999,999 = 100,999,998노드가 되므로 답은 1입니다.

입출력 예 #3

  • 8,000,000노드인 직원을 r = 29로 10년 동안 올리면 102,090,905노드가 됩니다.
  • r = 28이면 10년 뒤 94,447,324노드라 부족합니다. 따라서 답은 29입니다.

예시 테스트

#입력기대값
1[[60000000, 75000000, 52000000], 5]14
2[[99999999, 100000000, 120000000], 3]1
3[[30000000, 8000000], 10]29

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 13개도 함께 채점해요.