[BOJ 1654] 백준 랜선 자르기 풀이 - C++

사용언어 :  C++

 

 

문제풀이

* binary search(이진탐색) 사용

 

(1) for문으로 arr배열에 랜선길이 대입하기 (동시에 랜선 최대값 구하기)

int max_num = 0;
	for (int i = 0; i < K; i++) {
		cin >> arr[i];
		if (arr[i] > max_num) max_num = arr[i];
	}

 

(2) while문(이진탐색)으로 최대 랜선 길이 구하기 (N개와 비교)

	int max_length = 0;
	while (start <= end) {
		long long center = (start + end) / 2; //center값

		int count = 0; //해당 랜선길이로 자를 때 생기는 랜선이의 수
		for (int i = 0; i < K; i++) { //랜선 수 저장
			count += arr[i] / center;
		}
        
        //랜선 수 비교하기 
		 if (count < N) {
			end = center - 1;
		}
		else {
			start = center + 1;
			if(center>max_length)
				max_length = center;
		}
	}

 

전체코드

#include <iostream>
using namespace std;
#include <algorithm>
int K, N; int arr[10000];
int main() {
	cin >> K >> N;
	int max_num = 0;
	for (int i = 0; i < K; i++) {
		cin >> arr[i];
		if (arr[i] > max_num) max_num = arr[i];
	}
	long long start = 1;
	long long end = max_num;

	int max_length = 0;
	while (start <= end) {
		long long center = (start + end) / 2;

		int count = 0; //while문 안에
		for (int i = 0; i < K; i++) {
			count += arr[i] / center;
		}
		 if (count < N) {
			end = center - 1;
		}
		else {
			start = center + 1;
			if(center>max_length)
				max_length = center;
		}
	}
	cout << max_length;
}

 

 

---

총평

전에 풀어본 적이 있는 문제였다. 다시 풀어보니까 또 헷갈렸다 ㅎㅎ; 이제 이진탐색 자체는 다루기 수월해졌는데 가능 범위가 존재하고 그 사이에서 또 조건이 생길 경우에 혼란스러운 것 같다.. 그래도 이해한 내용 정리하면서 복습하면 잘 할 수 있을 것 같다!!

---

문제 출처

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

1654번: 랜선 자르기