티스토리 뷰
문제
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
문제 상황
- 입력받은 개수 N만큼 자른 랜선을 만들어야 할 때, 최대의 길이로 랜선을 자를 때 그 최대 길이를 계산한다.
해결 전략
- 방법은 두가지로 나눌 수 있다.
1) 길이를 정해 개수를 계산
2) 개수를 정해 길이를 계산
2번의 경우 개수가 정확히 N개일 때면 가능하지만 N보다 크거나 같다는 상황이므로 2번보단 1번의 방법이 유리하다. 길이의 경우 단순히 완전탐색하는 것이 아니라 이분 탐색을 통해 검색할 범위를 줄여준다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
from sys import stdin
input = stdin.readline
K, N = map(int, input().split())
K_list = [int(input()) for _ in range(K)]
K_list.sort()
min_len = 0
max_len = K_list[-1]
mid = max_len
def cutting(K_list, length, N):
cnt = 0
for i in range(len(K_list)):
cnt += (K_list[i]//length)
if cnt >= N : return True
return False
while True:
mid = ((min_len+max_len)//2)
if max_len == 1:
print(1) if cutting(K_list, max_len, N) else print(0)
break
elif max_len == 0:
print(0)
break
if cutting(K_list, mid, N):
min_len = mid
else :
max_len = mid
if max_len-min_len <= 1 :
print(max_len) if cutting(K_list, max_len, N) else print(min_len)
break
|
cs |
해설
- 0부터 최대 길이를 기준으로 이분탐색하며 길이를 검색하고, 그 길이가 가능한지 여부를 cutting 함수를 통해 판단한다. cutting이 가능하면 다시 그 조건을 base로 놓고 다시 연산하고, 불가능하면 ceiling으로 선언하여 다시 연산을 반복한다. 연산이 종료되는 조건은 min과 max의 차이가 1 이하인 경우인데, 같다는 조건을 사용하면 무한 루프에 빠지는 경우가 발생한다. 그래서 1차이 날 때에, max가 가능한지 여부를 통해 출력 내용을 결정한다.
새로 학습한 것 & 실수
- 99%에서 런타임 에러가 발생하였다. 런타임 에러가 발생하는 경우를 기존에는 index 에러로만 생각했는데 분모가 0인 경우도 런타임 에러가 발생함을 알았다.
- 조건을 조금 더 깔끔하게 줄 수 있을 것 같은데 우선 직관적으로 생각나는 방법으로 오류를 처리하였다.
'알고리즘 학습 > 백준 알고리즘' 카테고리의 다른 글
백준 알고리즘 - 공유기 설치 (2110) [Python] (0) | 2020.10.15 |
---|---|
백준 알고리즘 - 나무 자르기 (번호) [Python] (0) | 2020.10.15 |
백준 알고리즘 - 미로 탐색 (2178) [Python] (0) | 2020.10.08 |
백준 알고리즘 - 토마토 (7576) [Python] (0) | 2020.10.08 |
백준 알고리즘 - 섬의 개수 (4963) [Python] (0) | 2020.10.07 |
- Total
- Today
- Yesterday
- 리모컨#완전탐색#BOJ#Python
- 텀 프로젝트#백준알고리즘#Python
- django#slicing
- 터틀비치#리콘#xbox#controller
- django
- 종이자르기#분할정복#BOJ#Python
- 순열사이클#BOJ#Python
- 배열합치기#분할정복#BOJ#Python
- 반복수열#백준알고리즘#Python
- Triangle#Sorting#Codility#Python
- 미로 탐색#백준알고리즘#Python
- 랜선자르기#이분탐색#BOJ#Python
- 쿼드트리#BOJ#분할정복#Python
- Brackets#Stacks and Queues#Codility#Python
- 암호코드#dp#BOJ#Python
- 병든 나이트#BOJ#탐욕법#Python
- Distinct#Codility#Python
- API#lazy#
- 섬의개수#백준알고리즘#Python
- NumberofDiscIntersections#Codility#Sort#Python
- 날짜 계산#BOJ#완전탐색#Python
- 백준 알고리즘#BackTracking
- 토마토#백준알고리즘#Python
- 나무자르기#BOJ#이분탐색#Python
- 공유기 설치#BOJ#이분탐색#Python
- filter#isalnum#lower
- 파이썬알고리즘인터뷰#4장
- Swift#Tuples#Range
- N으로 표현#DP#Programmers#Python
- PassingCars#Codility#Python
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |