[c++] 13702번: 이상한 술집

https://www.acmicpc.net/problem/13702

13702번: 이상한 술집

 

문제 요약

 

주전자 용량은 동일하나 막걸리 용량은 랜덤.

막걸리 N 주전자를 주문하고, 친구들 K명에게 막걸리를 동일한 양으로 나눠준다. (주전자 속 남은 막걸리는 그냥 버린다.)

최대한 

 

범위

 

- 막걸리 주전자 개수 N (<=10,000)

- 은상 + 친구의 수 M (<=1,000,000)

- 막걸리 용량 (<= 1,000,000,000 자연수 혹은 0)

 

예시

 

주전자 3개(N) (1002, 802, 705ml)를 주문하고 401ml(최대 ml)로 동일하게 나눴을 때, 5명(M) 모두 마실 수 있다.

 

 

 

---

 

 

M명 모두에게 최대한 많은/동일한 양의 막걸리를 주고싶다.  

최대한 많은 양의 막걸리가 ML 일 때, M명이 마실 수 있는가?

 

여기서 주의할 점은 데이터 타입이다! 범위를 다시 살펴보면,

N은 최대 10,000  /  M은 최대 1,000,000  /  막걸리 용량은 최대 약 1,000,000,000(2^31 -1)

모든 입력이 최대라고 생각해보자.

만약 주전자 10,000개가 있는데, 각 주전자 속의 막걸리 용량이 모두 1,000,000,000ml 일때, 인원수가 1명이라면?

막걸리 양의 최댓값은? 1,000,000,000 x 10,000 = 10,000,000,000,000 ml 

→ int 형은 안된다. (-2,147,483,648 ~ 2,147,483,647)

→ long long 형을 사용했다. (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)

 

//13702번: 이상한 술집
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int n, m, x[10002];

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> x[i];
    }
}

bool calc(ll ML){
    if(ML == 0) return false; //0으로 나눌 수 없기 때문에 미리 없애기
    ll sum = 0;
    for(int i=0; i<n; i++){
        sum += x[i] / ML;
    }
    return sum >= m;
}

void solution(){
    ll L = 0, R = 10000000000000, ans = 0;
    while(L <= R){
        ll mid = (L+R)/2;
        if(calc(mid)){
            ans = mid;
            L = mid + 1;
        }else{
            R = mid - 1;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    solution();
    return 0;
}

 

 

---

 

long long int 란?

💡long long

long long 은 int형 연산에서 초과되는 범위를 다룰 때 사용한다.

Type	Byte	Range
(signed)int	4	-2,147,483,648 ~ 2,147,483,647
char	1	-128 ~ 127
short, short int	2	-32,768 ~ 32,767
long long	8	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
bool	1	true or false
float	4	3.4E+/-38(7개의 자릿수)
double	8	1.7E+/-308(15개의 자릿수)

 

 💡long long 과 long long int 의 차이점은?

 

동일한 타입이다. 차이점이 있다면 Specifier와 Type으로 나눌 수 있다는 것이다.

Specifier와 Type 간의 차이를 보자면, Specifier는 컴파일러에게 유형이 무엇인지 알려주는 방법이지만 같은 타입으로 다른 Specifier를 사용할 수 있다. 

출처: https://stackoverflow.com/questions/18971732/what-is-the-difference-between-long-long-long-long-int-and-long-long-i

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다. 만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
     언제나 환영합니다. 감사합니다. 화이팅!☃️