[백준] 1654. 랜선 자르기 (C++)

Key Point

• 자료형 범위를 고려해야한다.
• 이진탐색 범위 시작을 0으로 설정하면 입력값을 middle로 나눠주는 과정에서 DivisionByZero 에러가 발생할 수 있다. (입력으로 1 1   1이 들어오는 경우 middle이 0이 된다)

 

 

Idea

자료형 범위를 생각하지 않고 풀어서 틀렸던 문제다. 랜선의 길이는 int 범위 이내이기 때문에 int를 써도 상관없지만,  middle은 int형을 사용할 경우 오버플로우가 발생할 수 있다. 그 이유는 다음과 같다. 최악의 경우 end 값은 2**31-1이다. 이 때 start가 middle+1로 변경된다면 middle값은 (start + end) 가 되므로 오버플로우가 발생한다. 여기까지는 대부분 잘 확인하고 풀었을 것이다. 이 문제에서 골칫덩어리는 start와 end의 자료형이다. 어떤 자료형을 써야할까?? 정답부터 말하자면 둘 중 하나만 long long으로 설정해도 문제가 풀린다. while문 안의 middle 계산식을 보자. middle = (start+end)/2이다. while문이 한번 실행되어 end는 2**31-1, start는 middle-1값인 2**31 / 2 -1 이라고 가정해보자. start, end가 int형인 경우 다시 middle값을 구하기 위해 start+end를 하는 순간 오버플로우가 발생하게 된다. 하지만 둘 중 하나가 long long이라면 범위가 더 큰 long long으로 형변환 되기 때문에 오버플로우가 발생하지 않는다. middle에 값을 넣어주므로 middle만 long long이면 되지 않느냐? 라고 생각할 수도 있는데, 오버플로우는 더하는 그 순간에 발생하기 때문에 소용없다. 그렇다면 start, end가 long long이면 middle은 int여도 될까? 안된다. middle이 long long형인 값을 담지 못하기 때문이다.

 

이해가 안 된다면 다음 코드를 실행시켜보자.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <limits.h>

using namespace std;

int main(){
    cout << "test1 : "; // 더하는 순간 오버플로우 발생
    int test1_a = INT_MAX;
    int test1_b = INT_MAX;
    int test1_c = (test1_a + test1_b) / 2; 
    cout << test1_c << '\n';

    cout << "test2 : "; // 형변환 되었고 결과값이 int형 이내라서 오버플로우 발생X
    long long test2_a = INT_MAX;
    int test2_b = INT_MAX;
    int test2_c = (test2_a + test2_b) / 2; 
    cout << test2_c << '\n';

    cout << "test3 : "; // 둘 다 long long인 경우도 당연히 됨.
    long long test3_a = INT_MAX;
    long long test3_b = INT_MAX;
    int test3_c = (test3_a + test3_b) / 2; 
    cout << test3_c << '\n';

    cout << "test4 : "; // long long으로 자동 형변환되었지만 결과값이 int 범위를 초과하여 오버플로우 발생
    int test4_a = INT_MAX;
    long long test4_b = INT_MAX;
    int test4_c = test4_a + test4_b; 
    cout << test4_c << '\n';

    cout << "test5 : "; // 더하는 순간 오버플로우가 발생하여 더 광범위한 값에 캐스트해도 소용없음.
    int test5_a = INT_MAX;
    int test5_b = INT_MAX;
    long long test5_c = (test5_a + test5_b) / 2; 
    cout << test5_c << '\n';

    cout << "test6 : "; // 당연히 됨.
    long long test6_a = INT_MAX;
    long long test6_b = INT_MAX;
    long long test6_c = (test6_a + test6_b) / 2; 
    cout << test6_c << '\n';
    
    
    return 0;
}

 

+) 참고자료 https://dojang.io/mod/page/view.php?id=112 

C 언어 코딩 도장: 16.1 자료형의 확장 알아보기

 

 

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int>v;

int Search(long long start, long long end, int target) {
	long long middle = 0;
	long long result = 0;

	while (start <= end) {
		int cnt = 0;
		middle = (start + end) / 2; //middle값이 int범위 넘길수도

		for (int i = 0; i < v.size(); i++) {
			cnt += v[i] / middle;
		}
		if (cnt >= target) {
			result = middle;
			start = middle + 1;
		}
		else {
			end = middle - 1;
		}
	}
	
	return result;
	
} //N개보다 많이 만드는 것도 N개를 만드는 것에 포함됨.

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int k = 0, n = 0;
	int input = 0;

	cin >> k >> n;

	for (int i = 0; i < k; i++) {
		cin >> input;
		v.push_back(input);
	}
	
	sort(v.begin(), v.end());
	int max = *max_element(v.begin(), v.end());

	cout << Search(1, max, n) << endl;

	return 0;
}