해당 문제는 2진 탐색 알고리즘으로 풀 수 있다.
입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.
입력에선 랜선의 개수 K, 필요한 랜선의 개수 N, K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이를 받아야 한다.
이 때, 중요한 것은 2의31승 - 1 즉 21억 int의 최대값을 의미한다. 이는 K가 10,000이 입력되고
각 줄 마다 랜선에서 int의 최대값 ( 약 21억 ) 을 모두 더하면, 랜선의 총 길이는 21,476,983,953,647가 된다.
랜선의 총 덧셈한 이유는 차후 설명하겠다. 일단 알아만 두자
입력코드
#define MAX 10'001
int K, N;
int LanCable[MAX];
int HighLenght = 1;
void Input()
{
cin >> K >> N;
for (int i = 0; i < K; i++)
{
cin >> LanCable[i];
if (LanCable[i] > HighLenght)
HighLenght = LanCable[i];
}
}
입력 코드를 살펴보자 K,N을 일단 받아두고, LanCable은 K가 받을 수 있는 최대 입력값 + 1을 해준다.
HightLenght를 보면, LanCable을 입력 받을 때 마다 크기를 비교해준 후 넣어주고 있는데.
이유에 대해선 2가지로 나뉜다.
1. 우리는 최대 랜선의 값을 알아야 한다.
- 예시 입력으로 802,457,743,539 가 주어질 때, 802 이상으로 나눌 수 있는게 없기 때문이다.
2. 정렬 알고리즘을 사용시 오버헤드가 발생한다.
-> 최대값을 알아낸 후, 정렬을 돌리면 그에 따른 오버헤드가 발생하기 때문에 입력을 받을 때 마다 비교하는 것이.
더 빠르다.
풀이코드
int64 HighMid = 0;
void Solution(int64 low, int64 high)
{
if (low > high) return;
int64 mid = (low + high) / 2;
int64 sumCable = 0;
for (int64 i = 0; i < K; i++)
{
sumCable += LanCable[i] / mid;
}
if (sumCable >= N)
{
HighMid = max(HighMid, mid);
Solution(mid + 1, high);
}
else {
Solution(low, mid - 1);
}
}
void Solve()
{
Input();
Solution(1,HighLenght);
cout << HighMid << endl;
}
최초로 최대 길이를 High로 넣어주고 N의 최소값 1을 넣어서 재귀로 이진탐색을 진행한다.
이 때 SumCable을 LanCable마다 mid로 나눠준다.
예를들어 어떠한 Lancable이 802라고 한다면. 802/401은 2개가 나온다.
하지만 앞서 언급한 Lancable의 길이는 21억 까지 나올 수 있고, Mid가 2가 될 수있으며, K가 10,000 이라면 int로는
모두 담을 수 없다. 하여 long long 자료형으로 담아줘야 하며 이를 int64로 바꿔놨다. 추후 사용법은 전체코드를
보면 알 수 있다.
여하튼 이렇게 모두 더한 SumCable의 개수가 N과 같거나 높을 때 HighMid에 담아주고, max 함수를 사용하여 현재
mid와 Highmid를 비교한 후 더 큰 값을 넣어주었다.
간단히, 더 큰 길이를 저장한다고 보면 된다.
이후, low 값을 좁힌 뒤, 다시 재귀를 돌리고
만약 N보다 SumCable 개수보다 적다면, High 값을 좁혀준다.
전체코드
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>
using namespace std;
#define MAX 10'001
using int64 = __int64;
int K, N;
int LanCable[MAX];
// 가장 큰 값을 2분탐색 때 High로 넣기 위함.
int HighLenght = 1;
void Input()
{
cin >> K >> N;
for (int i = 0; i < K; i++)
{
cin >> LanCable[i];
if (LanCable[i] > HighLenght)
HighLenght = LanCable[i];
}
}
int64 HighMid = 0;
void Solution(int64 low, int64 high)
{
if (low > high) return;
int64 mid = (low + high) / 2;
int64 sumCable = 0;
for (int64 i = 0; i < K; i++)
{
sumCable += LanCable[i] / mid;
}
if (sumCable >= N)
{
HighMid = max(HighMid, mid);
Solution(mid + 1, high);
}
else {
Solution(low, mid - 1);
}
}
void Solve()
{
Input();
Solution(1,HighLenght);
cout << HighMid << endl;
}
int main()
{
Solve();
}

'프로그래밍-기본기 > 알고리즘(문제풀이)' 카테고리의 다른 글
| (백준) 2839 설탕 배달 c++ 그리디 알고리즘 (0) | 2023.09.19 |
|---|---|
| (백준) 2775 부녀회장이 될테야 C++ (0) | 2023.09.18 |
| (백준) 2108 통계학 C++ (0) | 2023.09.14 |
| (백준) 1874 스택 수열 C++ (0) | 2023.09.11 |
| (백준) 1676 팩토리얼 0의 개수 C# (2) | 2023.09.08 |