https://www.acmicpc.net/problem/1654
문제
> 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다.
> 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
> 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다.
> 그러나 K개의 랜선은 길이가 제각각이다.
> 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
> 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다.
(이미 자른 랜선은 붙일 수 없다.)
> 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.
> 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자.
> N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
> 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.접근
K개의 랜선의 길이가 주어질 때, 이 랜선들을 각각 x의 길이로 자르면(나누면) 나머지 버리고 y등분이 된다.
이 각각의 y등분을 다 더했을 때, N보다 크거나 같으면 원하는 결과를 얻었으니 일단 킵해두고 조금 더 x를 늘려(길이를 늘림)본다.
이는 이분탐색에서 중앙값의 오른쪽 범위를 고르는 것이다.
만약 N개보다 적게 만들어지면 길이를 더 줄여야 등분 수가 많이 나오기 때문에 x를 줄인다.
즉, 중앙값의 왼쪽 범위를 고르는 것이다.
이를 반복하면 최종적으로 left가 right보다 커지는데 그때 탐색이 끝나며 rst에 있는 최적의 값이 출력된다.
문제해결
> K와 N을 제외하고 변수를 long long 형으로 선언해준다.
> N개 이상의 랜선을 만들 수 있는 최대의 길이를 탐색하기 위해 Cut 메소드를 정의한다.
이분 탐색을 하므로 인자로 left, right, 각 탐색마다 가능한 최대의 길이를 넘길 rst를 가진다.
> 탐색의 끝나는 조건으로 left가 right를 넘어설 때로 잡고 이때 rst(최종 탐색까지 찾은 최대길이)를 반환다.
> 탐색을 하기위해 범위의 중앙값을 계산한다.
이 중앙값으로 각 랜선을 나눴을 때 나오는 수를 sum에 누적한다.
이 수는 각 랜선이 중앙값으로 나온 길이로 나눴을 때 몇 등분이 되는지에 대한 수 이다.
> 각각의 등분 수를 다 더했을 때(sum), N보다 크거나 같으면 원하는 결과를 얻을 수 있다는 길이이므로 일단 그 길이(mid)를 킾해놓고 최적을 찾기위해 범위를 수정한다.
> 랜선의 길이를 좀 늘려보기 위해 범위를 mid+1, right로 해서 다음 탐색을 한다.
> N보다 작다면 더 등분 수를 많이 만들어야하므로 길이를 줄이기 위해 범위를 left, mid-1로 수정해 탐색한다.
> 이제 main 함수에서 입력으로 K개의 랜선의 길이를 받아 벡터에 넣어준다.
> 입력받으면서 기준으로 삼을 가장 긴 랜선의 길이를 찾는다.
> 첫 탐색으로 랜선의 길이는 최소 1이고 위에서 최대 길이로 입력받은 가장 긴 랜선의 길이를 넣어 탐색한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int K, N;
long long Max = 0;
vector<long long> lan;
long long Cut(long long left, long long right, long long rst)
{
if (left > right) return rst;
long long mid = (left + right) / 2;
long long sum = 0;
for (int i = 0; i < K; i++)
{
sum += (lan[i] / mid);
if (sum >= N) return Cut(mid+1, right, mid);
}
return Cut(left, mid-1, rst);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> K >> N;
lan.resize(K);
for (int i = 0; i < K; i++)
{
cin >> lan[i];
Max = max(Max, lan[i]);
}
cout << Cut(1, Max, 1) << '\n';
}
후기
처음에 랜선의 길이 말곤 K와 N이 각각 만, 백만이라 int형으로 모든 변수를 줬다.
반례를 따지던 중, 만약 입력받은 랜선 중에 젤 긴게 2^31 -1이라면, 문제가 생긴다.
sum을 계산하는 부분에서 만약 mid가 1이라면 sum이 int형의 최대를 넘어가서 오버플로우가 생긴다.
그리고 mid를 구하는 부분에서도 만약 right가 2^31 -1 이고 left가 이 값의 1/2+1이라면 mid 계산에서 오버플로우가 발생할수 있다고 생각했다.
따라서 전부 long long으로 줬다.
그리고 이거 말고 오류로 divisionbyzero가 나왔다.
분모가 0이라는 뜻이므로 나누기 부분을 전부 따졌는데 mid값이 left가 0, right가 1이거나 둘다 0이면 0을 가지게 됐다. 그래서 조건으로 둘의 합이 1보다 작거나 같을 때 return하도록 했는데도 틀려서 보니 문제에 랜선의 길이는 "자연수"라고 줬다. 즉, 탐색에 초기로 들어갈 left값이 0이 불가능하다는 것이다.
그래서 추가한 조건식을 지우고 main문에 left에 1을 넣고 제출하니 맞았다. 문제를 잘 읽자.
