[백준 / BOJ] 14575 뒤풀이 (Rust)

문제

출처 : https://www.acmicpc.net/problem/14575

14575번: 뒤풀이

모든 사람은 각각 자신이 먹고싶어하는 최소주량 L 최대주량 R이 있다. 이 때, 도현이는 각각 의 사람들에게 최대 S만큼의 술을 나눠주며, 나눠준 술의 총 합을 정확히 T로 맞추는 S의 최솟값을 구하는 문제다.

---

풀이

문제에서 주어진 조건은 3가지 이다.

 

1. 모든 사람 i가 Li이상, Ri이하의 술을 받는다.

2. 모든 사람이 받은 술의 총합이 정확히 T 이다.

3. 어떠한 사람도 S를 초과한 술을 받으면 안된다.

 

S에 대해서 매개변수 탐색을 진행하며, 정해진 S가 위에서 정해진 조건을 만족하는지 체크하며 풀면 되는 문제다.

또한, 위에서 주어진 조건을 풀어보면, 각각의 사람들에게 술을 나눠줄때, 다음 조건을 만족해야 하는것을 알 수 있다.

 

조건 : "각각 의 사람들에게 최대 S만큼의 술을 나눠주며, 나눠준 술의 총 합을 정확히 T로 맞추는 S의 최솟값을 구하라"

 

위 조건을 의사 코드로 변환하면, 다음과 같은 코드가 나오게 된다. 

현재까지 나눠준 술을 divided, 할 때,

divided += min(s, Ri);

최종적으로, divided값이 T보다 크거나 같다면, 모든 사람에게 술을 정확히 T만큼 나눠줄 수 있는것을 알 수 있는데, 이유는 다음과 같다.

모든 사람의 하계 Li 를 전부 더한값이 T보다 작다면, divided를 전부 더한 값에서 일정한 값을 어떻게 빼도 T를 만들 수 있다.

 

문제를 풀때, 주의할 점이 있었는데..!

1. 모든 사람은 최소 Li이상의 술을 먹어야 하기 때문에, 각각의 사람들에게 술을 나눠 줄 때, s의 값이 Li보다 작아지지 않는지 체크해야한다.

2. 어떻게 해도 술을 나눠줄 S를 찾을 수 없는 경우를 체크 해줘야 하는데, 각 경우는 다음과 같다.

 2-1. 모든 사람의 Li를 전부 더한 값이 T보다 크다면, 어떻게 해도 T에 딱 맞게 술을 나눠줄 수 없다.

 2-2. 모든 사람의 Ri를 전부 더한 값이 T보다 작다면, 어떻게 해도 T에 딱 맞게 술을 나눠줄 수 없다.

 

주요 소스코드

fn is_beer_divide_able(m: i64, s: i64, pair_vec: &Vec<(i64, i64)>) -> bool{
    let mut divided = 0;
    for i in pair_vec {
        if s < i.0 {
            return false;
        }
        divided += min(s, i.1);
    }
    return m <= divided;
}

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/14575%20뒤풀이/main.rs

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃