문제 상황
파티에 성향이 서로 다른 세 그룹의 사람들이 참석한다고 가정해 보겠습니다.
첫 번째 그룹은 버터스카치 아이스크림만 좋아하고 다른 맛은 전혀 먹지 않습니다. 두 번째 그룹은 딸기 아이스크림만 싫어하며 나머지 모든 맛을 즐길 수 있습니다. 세 번째 그룹은 어떤 맛의 아이스크림이든 모두 좋아합니다.
첫 번째 그룹에서 x명, 두 번째 그룹에서 y명, 세 번째 그룹에서 z명이 파티에 오며, 모든 사람은 최소 한 개 이상 자신이 좋아하는 아이스크림을 받아야 합니다. 주최 측은 버터스카치 아이스크림 a팩, 초콜릿 아이스크림 b팩, 딸기 아이스크림 c팩을 준비했습니다.
이때 파티에 온 모든 사람이 각자 좋아하는 아이스크림을 하나씩 받을 수 있는지 판별하는 것이 목표입니다. 예를 들어 입력이 a = 6, b = 5, c = 5, x = 3, y = 8, z = 4라면 출력은 "Possible."(가능함)이 됩니다.
접근 방법
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 선호도가 가장 제한적인 그룹부터 순서대로 아이스크림을 배분한다고 생각하면 됩니다.
- 첫 번째 그룹은 버터스카치만 먹을 수 있으므로, 버터스카치 a개가 x명 이상이어야 합니다.
- 두 번째 그룹은 버터스카치 또는 초콜릿을 먹을 수 있으므로, 두 맛의 합(a + b)이 x + y명 이상이어야 합니다.
- 세 번째 그룹은 모든 맛을 먹을 수 있으므로, 전체 합(a + b + c)이 x + y + z명 이상이면 충분합니다.
따라서 다음 조건을 검사하면 됩니다.
if a < x or a + b < x + y or a + b + c < x + y + z, then:
print("Not Possible.")
Otherwise
print("Possible.")
누적합을 비교하는 이유는, 앞선 그룹이 이미 아이스크림을 가져간 뒤 남은 양으로 다음 그룹을 충족시킬 수 있는지를 순차적으로 확인하기 위해서입니다. 세 조건 중 하나라도 만족하지 못하면 누군가는 좋아하는 아이스크림을 받지 못하게 됩니다.
예제 구현
아래 C++ 코드로 위 로직을 직접 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int a, int b, int c, int x, int y, int z) {
if (a < x || a + b < x + y || a + b + c < x + y + z)
cout<<"Not Possible.";
else
cout<<"Possible.";
}
int main() {
int a = 6, b = 5, c = 5, x = 3, y = 8, z = 4;
solve(a, b, c, x, y, z);
return 0;
}입력
6, 5, 5, 3, 8, 4
출력
Possible.
위 입력에서 버터스카치 6개는 첫 번째 그룹 3명을 충분히 커버하고(a = 6 ≥ x = 3), 버터스카치와 초콜릿의 합 11개는 두 그룹의 합 11명을 정확히 충족하며(a + b = 11 ≥ x + y = 11), 전체 16개는 세 그룹의 합 15명보다 많습니다(a + b + c = 16 ≥ x + y + z = 15). 따라서 모든 사람이 아이스크림을 받을 수 있어 "Possible."이 출력됩니다.