프로그래머스 레벨3 예산

문제 : https://programmers.co.kr/learn/courses/30/lessons/43237

 

서론

이진탐색 문제인데,

뭔가 M/budgets.size()를 이용해서 풀 수 있을것 같아서 먼저 시도했다가 실패하고 이진탐색으로 해결

 

---

풀이

1번 조건이 해당되는지 확인 후에

2번 조건은 이진탐색으로 해결한다.

이때 이진탐색할 배열은 [1,2,3,4,.....m-1,m]이다.

반복되는 이진탐색에서 mid의 값은 정수상한액이며 2번 조건에 따라 정수상한액으로 총 예산을 계산한다.

long long cal(int mid, vector<int> &budgets){
    long long sum = 0;
    for(auto i : budgets){
        if(mid<i) sum +=mid;
        else sum += i;
    }
    return sum;
}

 

총 예산액이 M과 동일하면 mid는 정답이며 이진탐색을 빠져나온다.

총 예산액이 M보다 크거나 작으면 이진탐색을 계속해준다.

 

---

디버깅

1. 총 예산액이 mid와 동일한 경우가 없을때

 

총 예산액이 mid와 동일한 경우가 없을 수 있다. 정답은 mid의 최대값을 찾는 것이므로 반복문에서 총 예산액이 M보다 작거나 같을때는 answer값을 mid로 갱신해주고 클때는 갱신하지 않아야 한다.

클때도 갱신하게 되면 총 예산액이 M을 초과했을때 mid값이 answer가 된 후 반복문의 start<=end 조건을 만족하지 못해서 answer가 그대로 출력될 수 있다.

 

반례

budgets = [1,2,3,4], M = 8;

정답2, 오답3

 

수정 전

while (start <= end) {
	mid = (start + end) / 2;
	sum = cal(mid, budgets);
	//cout<<mid<<" "<<sum<<endl;
	answer = mid;
	if (sum == M) break;
	else if (sum < M) start = mid + 1;
	else if (sum > M) end = mid - 1;
}

 

수정 후

while (start <= end) {
	mid = (start + end) / 2;
	sum = cal(mid, budgets);
	//cout<<mid<<" "<<sum<<endl;
	if (sum == M) {
		answer = mid;
		break;
	}
	else if (sum < M) {
		answer = mid;
		start = mid + 1;
	}
	else if (sum > M) end = mid - 1;
}

 

2. 총 예산액의 자료형

 

총 예산액의 자료형을 int로 만들면 효율성테스트에서 실패가 뜬다.

long long으로 수정해야한다.

 

---

구현

// c++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long cal(int x, vector<int> &budgets){
    long long sum = 0;
    for(auto i : budgets){
        if(x<i) sum +=x;
        else sum += i;
    }
    return sum;
}

int solution(vector<int> budgets, int M) {
    int answer = 0;
    long long sum = 0;
    // 1번
    for(auto i : budgets){
        sum += i;
        answer = max(answer, i);
    }
    if(sum <=M) return answer;
    else answer = 0;
    
    // 2번
    int start = 1;
    int end = M;
    int mid = (start+end)/2;
    while(start<=end){
        mid = (start+end)/2;
        sum = cal(mid, budgets);
        //cout<<mid<<" "<<sum<<endl;
        if (sum == M) {
            answer = mid;
            break;
        }
        else if(sum<M) {
            answer = mid;
            start = mid +1;
        }
        else if(sum>M) end = mid - 1;
    }
    
    return answer;
}