개요

백준 1654번: 랜선 자르기

• 입력
  첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

• 출력
  첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

접근 방식

이분탐색을 이용해 답을 구하는 문제이다.
답이 될수 있는 최대값이므로 조건을 만족시킬때마다 low에 mid를 넣고 아니면
high에 mid를 넣는식으로 low와 high의 차이가 1날때까지 반복하면 low에 최대값이 들어간다.

각 탐색마다 랜선의 길이를 mid값으로 나눈 값의 총합이 N보다 많아지면 low = mid
총합이 N보다 적어지면 high = mid

코드

#include<iostream>

using namespace std;
int K, N, Max=0;
int inputArr[10001];

void input() {
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> inputArr[i];
		//제일 큰 입력값 얻기 -> high값에 쓸 것
		Max = Max > inputArr[i] ? Max : inputArr[i];
	}
}

void solution() {
	//각 랜선 길이는 21억까지 될 수 있으므로 mid구할때 오버플로 날수 있으므로 long long으로 선언 
	//high를 입력값의 최대값으로 정하면 안됨 low를 답으로 배출할텐데 high가 처음에 답이들어있으면 답을 못구함
	long long low = 0, high = 2'200'000'000, mid=0, tmpSum=0;
	while (low + 1 < high) {
		mid = (low + high) / 2;
		for (int i = 0; i < K; i++) {
			tmpSum += inputArr[i] / mid;
		}
		//자른 갯수가 N개보다 많다면 범위를 높여야하므로 
		if (tmpSum >= N) low = mid;
		else high = mid;
		tmpSum = 0;
	}
	cout << low;

}

int main() {
	input();
	solution();
}

문풀후생

이번에도 저번 백준6236(용돈 관리) 문제 처럼 low와 high값의 초기설정을 실수해서
좀 틀렸었다.

이번엔 high에 입력값중 제일 큰 값을 넣어줬는 데
입력값중 제일 큰 값이 답일 경우 high값 -1로 답이 나와서 오답이 난 것이다.