[BOJ/C++]1654(랜선 자르기)

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

1. 만들 수 있는 최대 랜선의 길이 -> 이분 탐색 또는 DP 예상
2. k개의 랜선으로 같은 길이의 n개의 랜선으로 만듦 -> 이분 탐색, count를 기점으로 n 이상인지 여부에 따라 범위 수정

• 다시금 자료형의 중요성을 생각하게 되는 문제였습니다. 자료형 Overflow 등으로 문제가 틀리는 경우가 정말 가끔 있으니 참고하시면 됩니다.

1번 오답(50%)

#include<iostream>
#include<algorithm>
using namespace std;

int n, k;
int line[10001];
long long answer = 0;

void input() {
	cin >> k >> n;
	for (int i = 0; i < k; ++i) cin >> line[i];
	sort(line, line + k);
}

void solution() {
	input();
	int low = 0, high = line[k - 1];
	while (low <= high) {
		int mid = (low + high) >> 1;
		int cnt = 0;
		for (int i = 0; i < k; ++i) {
			cnt += line[i] / mid;
		}
		if (cnt < n) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
			if (mid > answer) answer = mid;
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

어디서 틀렸는지 한참을 고민했고, mid에서 2^31-1의 근사치 2개를 더할 경우에 Overflow가 발생할 수 있다는 것을 생각

따라서 자료형을 long long(코드에서는 #define으로 줄임)을 사용하여 다시 풀었고, 정상적인 결과 확인

2번 정답

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

int n, k;
int line[10001];

void input() {
	cin >> k >> n;
	for (int i = 0; i < k; ++i) cin >> line[i];
}

void solution() {
	input();
	sort(line, line + k);
	ll low = 1, high = line[k - 1];
	int answer = 0;
	while (low <= high) {
		ll mid = (low + high) >> 1;
		int cnt = 0;
		for (int i = 0; i < k; ++i) {
			cnt += line[i] / mid;
		}
		if (cnt >= n) {
			if (mid > answer) answer = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}