반응형
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
www.acmicpc.net
이분탐색 문제. 이분탐색으로 찾아야 할 값은 '랜선의 길이'이고, 이분탐색의 기준은 '랜선의 개수'가 된다.
랜선의 길이 최솟값은 1, 최댓값은 주어진 랜선 길이로 정한 뒤
mid = (최솟값 + 최댓값) // 2로 잘라낼 길이를 정하고, 랜선 길이에서 mid만큼 잘라낼 경우 몇 개가 나오는지 합계를 구하면 된다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 입국 심사 (Level 3) (0) | 2020.01.11 |
|---|---|
| [Python] 백준 9012. 괄호 (0) | 2020.01.10 |
| [Python] 백준 2231. 분해합 (0) | 2020.01.08 |
| [Python] 프로그래머스. 징검다리 (Level 4) (0) | 2020.01.07 |
| [Python] 프로그래머스. 멀리 뛰기 (Level 3) (0) | 2020.01.06 |