BOJ 백준 3090 : 차이를 최소로
Updated:
시작하면서
이번 문제는 이분 탐색 카테고리 문제이다. 원래는 우선 순위 큐 문제로 알고 골랐었는데, 문제를 풀다 보니 우선 순위 큐보다는 이분 탐색에 가까운 문제였다.
개념
이분 탐색은 정렬되어 있는 자료 구조에서 특정한 데이터를 찾으려 시도할 때, 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것을 말한다.
탐색의 범위가 절반씩 줄어가므로 시간 복잡도는 O(logn)이다.
문제 이해
문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 3가지이다.
- N : 배열의 길이
- T : 감소시키는 연산의 수
- A : 배열
이 변수를 가지고 답을 출력해야 한다.
문제 아이디어
해당 문제는 인접한 수의 차이 값들 중 최대값을 가장 작게 만들어야 한다.
- 기준 값((최대값 + 최소값) / 2)을 정하고, 차이 값들을 비교한다.
- 이 성립하면 기준 값(최대값)을 낮춰서 다시 시도하고, 성립하지 않으면 기준 값(최소값)을 높여서 다시 시도한다.
- 기준 최소값이 최대값보다 커지면 종료한다.
해결
#include <iostream>
using namespace std;
int N, T;
int inputArr[100001] = { 0, };
int copyArr[100001] = { 0, };
void Input();
void SolveProblem();
void PrintArray(int *arr);
bool CheckCondition(int standardValue);
void CopyArray(int *start, int *destination);
int main()
{
//sync off
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
SolveProblem();
PrintArray(copyArr);
}
void Input()
{
cin >> N >> T;
for (int i = 0; i < N; i++)
{
cin >> inputArr[i];
}
}
void SolveProblem()
{
int low = 0, high = 1e9;
int standardValue = 0;
int minimumDifference = 1e9;
// 기준 최소 값이 최대 값을 넘길 때까지 반복한다.
while (low <= high)
{
// 기준 값 : (최소 + 최대) / 2
standardValue = (low + high) * 0.5f;
CopyArray(inputArr, copyArr);
if (CheckCondition(standardValue) == true)
{
// 조건에 맞을 경우
// 좀 더 좋은 조건이 있을 수 있으니 high를 1 줄여서 다시 시도한다.
high = standardValue - 1;
}
else
{
// 조건에 맞지 않을 경우 low를 1 늘려서 다시 시도한다.
low = standardValue + 1;
}
}
CopyArray(inputArr, copyArr);
CheckCondition(low);
}
void PrintArray(int *arr)
{
for (int i = 0; i < N; i++)
{
cout << arr[i] << " ";
}
}
bool CheckCondition(int standardValue)
{
int count = 0;
// 좌측에서 우측으로 값을 비교한다.
for (int i = 0; i < N - 1; i++)
{
if (copyArr[i + 1] - copyArr[i] > standardValue)
{
count += copyArr[i + 1] - copyArr[i] - standardValue;
copyArr[i + 1] = copyArr[i] + standardValue;
}
}
// 우측에서 좌측으로 값을 비교한다.
for (int i = N - 1; i > 0; i--)
{
if (copyArr[i - 1] - copyArr[i] > standardValue)
{
count += copyArr[i - 1] - copyArr[i] - standardValue;
copyArr[i - 1] = copyArr[i] + standardValue;
}
}
// 기준 횟수 이내에 완성되면 true를 반환한다.
if (count <= T)
{
return true;
}
else
{
return false;
}
}
void CopyArray(int *start, int *destination)
{
for (int i = 0; i < N; i++)
{
destination[i] = start[i];
}
}
코드는 설명 그대로 구현이고, 다음 부분에서 실행 시간을 줄일 수 있었다.
void SolveProblem()
{
...
if (CheckCondition(standardValue) == true)
{
// 조건에 맞는 배열은 결과 값에 넣어주고,
// 좀 더 좋은 조건이 있을 수 있으니 high를 1 줄여서 다시 시도한다.
CopyArray(copyArr, resultArr);
high = standardValue - 1;
}
...
}
최초에는 resultArr를 따로 두어서 결과에 만족하는 배열이 있을 때마다 넣어주었다. 백준에서 문제를 제출했을 때 내 수행 시간은 32ms 였는데, 최상위권은 대부분 28ms 의 수행 시간이 나왔다.
무엇이 다른가 코드를 비교해보았고, 조건을 만족했을 때마다 굳이 배열에 따로 복사를 해주지 않아도 되는 것을 알았다. 그래서 코드를 다음과 같이 수정했다.
void SolveProblem()
{
...
if (CheckCondition(standardValue) == true)
{
// 조건에 맞을 경우
// 좀 더 좋은 조건이 있을 수 있으니 high를 1 줄여서 다시 시도한다.
high = standardValue - 1;
}
...
// 최적의 값을 구하는 조건으로 배열 확인을 진행해서,
// copyArr에 답을 복사한다.
CopyArray(inputArr, copyArr);
CheckCondition(low);
}
위와 같이 마지막에 CheckCondition 함수의 조건을 최적의 결과가 나온 마지막 low 값을 넣어서 한 번 더 진행했다. 그럼 copyArr에 정답이 들어가게 되고 해당 값을 출력하면 된다.
하지만 수행 시간은 줄지 않았다. 하지만 resultArr를 지운만큼의 메모리 이득을 취할 수 있었다.
마치며
우선 순위 큐를 풀고 싶어서 골랐는데 이분 탐색이라 1차 당황했고, 생각보다 문제가 쉽지 않아서 2차 당황했다. 57%의 정답률 문제라서 무시했는데 역시 콘테스트 문제들은 문제의 깊이가 다른 듯 하다.
알고리즘 공부를 다시 시작한지도 약 3주째 접어들어가는데 아직도 옛날 감을 찾으려면 더 열심히, 많이 해야한다는게 느껴진다. 화이팅하자.
Leave a comment