BOJ/백준 1654 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

언어 : C++14

환경 : ideone.com - https://ideone.com

 

Parametric Search를 이용한 문제입니다.

아이디어는 입력받는 값 중 최솟값은 1, 최댓값을 end 변수에 넣고 중앙값을 구해준 다음

배열의 원소를 중앙값으로 나눈 값을 cnt 변수에 더해줘서 몇 개의 랜선을 만들 수 있는지 계산했다.

cnt 값이 n값 즉 필요한 랜선의 개수보다 많으면 start에 center + 1의 값을 넣어주고 그리고 이때 현재 solve의 값보다
center의 값이 크다면 solve값을 center 값으로 바꿔준다. (참고로, 왜 한 번에 답을 안 구하고 값을 계속 바꿔 주냐면

값을 최적화시켜서 답을 결정해야 하기 때문입니다.)

필요한 랜선의 개수보다 적으면 end에 center - 1을 대입해주고 답을 구할 때까지 반복합니다.

 

코드

#include <iostream>
using namespace std;
int arr[10001];
int main() {
	int k, n, max = 0, solve = 0;
	scanf("%d %d", &k, &n);
	for (int i = 0; i < k; i++) {
		scanf("%d", &arr[i]);
		if (arr[i] > max) {
			max = arr[i];
		}
	}

	long long start = 1, end = max;
	while (start <= end) {
		long long center = (start + end) / 2;
		int cnt = 0;
		for (int i = 0; i < k; i++) {
			cnt += arr[i] / center;
		}
		if (cnt >= n) {
			start = center + 1;
			if (center > solve) {
				solve = center;
			}
		}
		else {
			end = center - 1;
		}
	}
	printf("%d\n", solve);
	return 0;
}

결과

예전에 푼 문제라 헤더랑 namespace 부분 빼고는 C 코드로 작성되어 있다.

처음 풀 때 잘 모르고 선형탐색으로 풀다가 시간 초과만 나왔던 기억이 있다