문제 이해 단계
해당 문제는 이해하는데만 해도 30분 정도 걸렸다.
요약하자면 N일 동안 용돈 관리를 하는데, 그날 사용해야 할 금액이 존재한다.
용돈 관리를 하다가 돈이 부족하면 금액 K를 인출한다.
이때, 인출은 M번까지만 가능하다.
이때 조건을 만족하는 최소 금액 K를 구하는 것
문제 접근 단계
1.
위 문제 조건에 부합하는 금액 K를 찾는 것이기 때문에
K의 범위를 점점 줄여나가면서 찾는 탐색을 할까?라고 생각했고,
그중에서 1초라는 짧은 제한시간 때문에
"빠르게 탐색해야 하는 이진탐색 문제가 아닐까 생각했다.
2.
금액 K의 범위를 생각해 봤는데,
그날 써야 하는 금액보다 인출금액 K가 작으면 조건이 성립을 안 한다.
그렇기 때문에, 각 날의 써야 하는 금액 중
가장 높은 금액보다는 무조건 크거나 같아야 한다.
또한 극단적으로 M이 1일 때, (한 번의 인출로 N일을 사용해야 하는 경우)가
인출금액 K가 가장 클 때이다.
이럴 경우는 각 날의 써야 하는 금액의 합과 같아야만
M=1일 때 N일을 버틸 수 있다.
그러므로 K의 범위는
(하루 소비 비용 중 가장 높은 값) ≤ K ≤ (모든 날의 하루 소비 비용 값의 합)
이다.
이 조건 덕분에 이진 탐색을 시작할 범위를 제한할 수 있어
시간을 획기적으로 줄일 수 있다는 생각을 했다.
3.
해당 금액 K가 조건에 부합하는지 확인하는 법을 생각해 봤을 때,
일단 계산하는 경우는 두 가지가 있다.
for (int i = 0; i < N; i++) {
if (keyPrice - arr[i] < 0) // 그 날 가지고 있는 돈이 부족한 경우
{
count++; // 인출 횟수 추가
keyPrice = middle - arr[i]; // 돈을 인출하고 그 날 소비비용을 뺀다.
}else // 돈을 인출하지 않고 뺀다
keyPrice -= arr[i];
}남은 돈으로 오늘 써야 할 소비 비용이 가능한가의 여부이다.
변수에 대해서는 나중에 설명하겠지만,
현재 가진 남은 돈을 나타내는 keyPrice, 현재 금액 K를 나타내는 middle,
인출 횟수 count로 코드를 작성했다
4.
1 <=M <=N이라는 M번을 맞추기 위해
남은 돈을 넣고 K원을 인출 가능하다면 조건을 눈여겨보자.
문제에서는 정확히 M번을 맞추라고 했지만,
M <=N이기 때문에, count가 M을 초과하지만 않는다면 어떻게든 M번을 맞출 수 있다.
예를 들어 N=5 M=3 일 때, 금액 K가 인출을 한 번만 해도 될 정도로
K가 높다고 가정해 보자. (M=1일 때와 같이)
하지만 조건 중에 남은 돈이 많아도 반납하고
다시 인출이 가능하기 때문에 의도적으로 M=3이 가능하다.
즉, count <= M 이기만 하면 조건이 부합한다고 생각해도 된다.
if (count <= M) {
ans = middle;
end = middle - 1;
}else
{ start = middle + 1;
}그래서 위와 같이 이진 탐색의 범위를 count <=M로 판단하였다.
문제 구현 단계
#include <iostream>
using namespace std;
// 이진 탐색 및 K 값을 찾는 함수
int priceSearch(int arr[], int N, int M, int maxPrice) {
int sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[i]; // 최대범위 설정을 위한 sum
}
if (M == 1) return sum; // M = 1일때는 sum이 K이다.
int start = maxPrice; // 최소 범위를 가장 큰 값을 설정
int end = sum; // 최대 범위 = sum으로 설정
int ans = sum; // 정답을 담을 배열
while (start <= end) // 이진탐색 완료 조건{
int count = 1;
int middle = (start + end) / 2; // N/2를 뜻하는 middle 선언
int keyPrice = middle; // 현재 인출금액 K를 keyPrice로 저장
for (int i = 0; i < N; i++) {
if (keyPrice - arr[i] < 0) {
count++;
keyPrice = middle - arr[i];
}
else
keyPrice -= arr[i];
}
if (count <= M) {
ans = middle; // 조건에 부합했으므로 middle 값을 정답으로 설정
end = middle - 1; // 이진탐색 끝범위를 middle - 1로 줄임
}
else {
// 해당 금액K가 너무 작은 경우
start = middle + 1; // 시작범위를 조정하여 높은 값으로
}
}
return ans;
}
int main() {
int N, M;
cin >> N >> M;
int* arr = new int[N];
int maxPrice = 0;
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (arr[i] > maxPrice) maxPrice = arr[i]; // 가장 큰 수를 찾는 작업
}
cout << priceSearch(arr, N, M, maxPrice) << endl;
}전체 코드는 위와 같다.
첫째 줄에는 N, M을 입력받고 N 값을 토대로
배열 arr을 생성해 그날 사용해야 할 금액을 입력받는다.
이때, maxPrice와 비교하여 해당 배열 중 가장 큰 값을 저장해 둔 뒤,
이를 priceSearch 함수의 인자로 넘겨준다.
이는 이진 탐색에 필요한 start, end 범위를 설정하기 위함이다.
이진 탐색에 관해서는 따로 서술해두지 않고
나중에 개념으로 정리해 두겠다.
여기서 봐야 할 점은 이진탐색의 범위를 줄이는 조건으로
count <=M 참, 거짓 유무로 판단했다는 점이다.
또한 count = 1로 선언한 이유는
무조건 시작할 때 한 번의 인출은 하고 시작하기 때문이다.
탐색을 하다가 count <= M 조건이 부합한다는 것은
K값이 될 수 있다는 것이기 때문에 일단 ans에 담아두고 end의 범위를 줄인다.
end의 범위를 줄여서 만약 조건에 부합한 K값 후보가 나왔다면
이는 필히 이전 K값 후보보다는 작은 수라는 것이다.
따라서 K의 최솟값을 찾는 해당 문제에서는
당연히 ans를 현재 K 후보 값으로 업데이트해 준다.
이 모든 과정을 끝내면 ans를 반환하여 답을 구한다.
시행착오
이 문제의 알고리즘을 생각하고 구현하는 것은 오래 걸리지 않았는데,
자꾸 틀렸다고 떠서 시간이 엄청 오래 걸렸다.
for (int i = 0; i < N; i++) {
keyPrice -= arr[i];
if (keyPrice <= 0) {
count++;
keyPrice = middle;
}else
keyPrice -= arr[i];
}틀렸던 부분은 이 부분이었다.
여기서 keyPrice를 뺀 후 0보다 작으면
인출을 해주고 값을 초기화하면 된다고 생각했다.
하지만 이런 식으로 계산하면, 다음 날 계산을 할 때
keyPrice가 middle - arr [i]가 아닌 middle이 들어간다.
즉, 전에 그전 날 써야 하는 비용을 쓰지 않은 상태가 되는 것이었다.
테스트 케이스에서는 정상적으로 500이 나와서 이를 알아차리는데 오래 걸렸다.
for (int i = 0; i < N; i++) {
if (keyPrice - arr[i] < 0) // 그 날 가지고 있는 돈이 부족한 경우
{
count++; // 인출 횟수 추가
keyPrice = middle - arr[i]; // 돈을 인출하고 그 날 소비비용을 뺀다.
}else
// 돈을 인출하지 않고 뺀다
keyPrice -= arr[i];
}그래서 위에서 서술했던 코드와 같이 값을
keyPrice = middle - arr [i]로 하니 정상적으로 정답이 도출됐다.
이런 부분에서 애먹은 것이 정말 짜증 났지만 좋은 경험이었던 것 같다.