-
[백준] 1654: 랜선 자르기데일리 커밋 2022. 1. 11. 12:59
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
여태까지 푼 문제들 중에 가장 오래 걸렸다.
이진 분류로써 풀어야 한다는 것은 알겠는데 머릿속에 알고리즘이 그려지지 않았다.
랜선 수가 n보다 많아도 되지만, 많다는 것은 더 크게 자를 수 있다는 소리다. 즉 랜선의 길이가 더 길어도 된다는 말이다.
따라서 start = end 라면 가장 최적의 길이를 구할 수 있게 된다.
k,n = map(int,input().split()) #k = 가지고 있는 랜선 수, n = 필요한 랜선 수 num = [int(input()) for i in range(k)] #랜선의 길이 start, end = 1, max(num) while (start<=end): mininum = [] mid = (start+end)//2 for i in num: mininum.append(i//mid) #랜선 길이를 중간값으로 나눈 값을 저장한다. if sum(mininum) >= n: #나눈 값들을 다 합하면 총 랜선 수가 나온다. start = mid+1 # 총 랜선 수가 n보다 크다면 더 크게 잘라야 한다. else: end = mid-1 #총 랜선 수가 n보다 작다면 더 작게 잘라야 한다. print(end)
'데일리 커밋' 카테고리의 다른 글
[백준] 2798번: 블랙잭 (0) 2022.01.13 [백준] 4153번: 직각삼각형 (0) 2022.01.12 [백준] 1436번: 영화감독 숌 (0) 2022.01.10 [백준] 1181번: 단어 정렬 (0) 2022.01.09 [백준] 1085번: 직사각형에서 탈출 (0) 2022.01.08