BOJ (C/C++) 1654번: 랜선 자르기

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

1654번: 랜선 자르기

---

풀이

이분 탐색으로 구현. 알고리즘 자체는 어렵지 않으나 사소한 것들을 놓쳐서 오래 걸림.

 

밑에는 풀면서 놓쳤던 오류들

 

- start=0으로 할 때에 mid=0이 될 수 있어 divided by zero 오류 가능성 존재.
   -> start=1로 선언- start=1로 둘 때 mid 값 계산 시 int형 오버플로우 가능성 존재. (채점 시 시간초과)
   -> start, mid, end 모두 long long 으로 선언

- 답은 가장 작은 입력값보다 작을 수 있음 (ex 2 4 / 4 8  --> ans : 2)
   -> start = 1로 선언

결론 : 되도록이면 다 long long으로 선언하세요...

 

- 잘린 갯수가 int형보다 많을 수 있음 -> long long 선언

- while(start<end)의 조건때문에 start==end일 때의 값이 정답일 때 오류 -> while(start<=end)로 지정

 

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> V;
int length(int K, int N) {
	// 이분탐색을 위한 정렬
	sort(V.begin(), V.end());

	long long int mid, cnt, max = 1, start = 1, end = V[K - 1];

	// Binary Search
	while (start <= end) {
		cnt = 0;
		mid = (start + end) / 2;

		for (int i = 0; i < K; i++)	cnt += (V[i] / mid);

		// 잘린 갯수가 많을 때도 포함해야 함.
		if (cnt >= N) {
			start = mid + 1;			
			if (mid > max) max = mid; // 가장 큰 값 구하기
		}
		else end = mid - 1;
	}
	return max;
}
int main() {
	int N, K, len;
	scanf("%d %d", &K, &N);
	for (int i = 0; i < K; i++) {
		scanf("%d", &len);
		V.push_back(len);
	}
	printf("%d", length(K, N));

	return 0;
}