백준 1654번 랜선 자르기 [C/C++]

1654번: 랜선 자르기

문제

주어진 K개의 랜선으로 N개의 랜선을 만들어라. 300cm 랜선으로 140짜리 랜선을 두 개 만들면 나머지 20는 버려야 한다.

 

입력

K는 1이상 10,000이하의 정수이다. N은 1이상 1,000,000이하이다. 

 

출력

N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

풀이

문제를 읽어도 무엇을 사용해야 하는지 감이 안잡혀서, 알고리즘 분류를 보았는데 이분 탐색을 활용한다고 한다. 

 

다른 블로그에서 이분 탐색 구현법을 살펴볼 때, 배열에는 정렬된 데이터가 저장되어 있고, 찾고자 하는 값이 정해져 있다. 그래서  mid변수를 통해 배열에 접근하여 맞는 값을 찾는 것이 일반적인 구현법이었는데, 이것을 문제에 맞게 적용하는 것에 어려움이 있었다.

 

그래서 배열에 정렬된 값을 넣고 최대값을 넣으려는 발상을 했지만, 너무 값의 범위가 커져서 다른 블로그의 풀이를 참고해보니 k개의 랜선의 개수를 배열로 잡고 입력되는 길이들을 배열에 저장해주는 것이었다.

 

그리고 mid를 변수를 통해서 배열에 저장되어 있는 랜선길이들을 통해 최대값을 구하는 것이었다.

이 부분에서 배웠던 점은 mid라는 변수가 굳이 배열에 접근해야 되는 것이 아니다. 즉, start와 end의 값을 통해 적절히 mid의 값을 변경해가면서 원하는 값을 찾는 것이 중요하다.

 

아래 코드는 성공한 코드입니다.

#include <iostream>
using namespace std;	

int lan_numer[10001];

long long c_binary_search(long long start, long long end, int target, int k)
{
	long long middle;
	//start가 end를 넘어가게 된 순간 값을 찾은 것임.
	while (start <= end) {
		int count = 0;
		middle = (start + end) / 2;

		for (int i = 0; i < k; i++) {
			count += lan_numer[i] / middle;
		}

		// start가 end를 넘어가게 된 순간 값을 찾은 것이기에, 
		// count와 target이 같다고 해도 result가 다를 수 있어서 계속 반복문을 돌아야함.
		if (count >= target) start = middle + 1;
		else end = middle - 1;
	}

	return end;
}

int main()
{
	int k, n;
	int max = 0;
	cin >> k >> n;

	for (int i = 0; i < k; i++) {
		cin >> lan_numer[i];
		if (max < lan_numer[i]) max = lan_numer[i];
	}

	// 랜선의 길이는 1 ~ 2^31-1 범위의 자연수 즉, lan_num배열에 있는 길이는 int형을 초과할 일이 없지만, 
	// start와 end계산을 할 때는 값이 넘어갈 수 있음.
	long long result = c_binary_search(1, max, n, k); //넘어온 값은 int겠지만 long long으로 함. 
	printf("%d", result);

	return 0;
}

 

---

 

그리고 문제를 풀면서 막힌 곳이 있다.

 

틀린코드

long long binary_search(long long start, long long end, int n, int k)
{
    while (start <= end) {
        int count = 0;
        long long middle = (start + end) / 2;

        for (int i = 0; i < k; i++) {
            count += num_of_lan[i] / middle;
        }

        if (count > n) start = middle + 1;
        else if (count == n) return middle;
        else end = middle - 1;
    }

    return end;
}

 제일 처음에는 count와 n이 같으면 맞는 답 아닌가? 라는 생각을 했다. 하지만 그러면 안되는게 예를들어서 start가 1, end가 800이고 end가 값 700을 찾아가게 만들때 end값이 705, 702, 700으로 줄어드는 모습을 확인할 수 있는데 이 모든 과정에서 count와 n값은 같으므로 count == n일 떄 break를 하게 되면 틀린값이 출력된다. 그래서 end값이 start값보다 작아지는 경우가 되야, 맞는 값을 찾아간 것이라 볼 수 있다.