문제 개요
세 가지 서로 다른 종류의 컵(p[])과 접시(q[]), 그리고 선반의 개수 m이 주어졌을 때, 모든 컵과 접시를 주어진 선반에 깔끔하게 정리할 수 있는지 판단하는 문제입니다.
배치가 '깔끔하다'고 인정되려면 아래 세 가지 규칙을 모두 만족해야 합니다.
- 규칙 1: 하나의 선반에는 컵과 접시를 함께 둘 수 없습니다.
- 규칙 2: 하나의 선반에는 최대 5개까지의 컵만 놓을 수 있습니다.
- 규칙 3: 하나의 선반에는 최대 10개까지의 접시만 놓을 수 있습니다.
입력 및 출력 예시
예시 1
p[] = {4, 3, 7}
q[] = {5, 9, 10}
m = 11출력:
Yes
설명: 컵은 총 14개이므로 3개의 선반이 필요하고, 접시는 총 24개이므로 역시 3개의 선반이 필요합니다. 따라서 필요한 선반은 총 6개로, 주어진 선반 개수 m=11보다 적습니다. 그러므로 출력은 Yes입니다.
예시 2
p[] = {5, 8, 5}
q[] = {4, 10, 11}
m = 3출력:
No
설명: 컵은 총 18개이므로 4개의 선반이 필요하고, 접시는 총 25개이므로 3개의 선반이 필요합니다. 따라서 필요한 선반은 총 7개로, 주어진 선반 개수 m=3보다 많습니다. 그러므로 출력은 No입니다.
풀이 방법
핵심 아이디어는 매우 간단합니다. 먼저 모든 컵의 총개수(sump)와 모든 접시의 총개수(sumq)를 각각 구합니다.
컵은 한 선반에 최대 5개까지만 놓을 수 있으므로, 컵을 모두 수용하는 데 필요한 선반의 최소 개수는 올림 나눗셈 공식인 (sump + 5 - 1) / 5로 구할 수 있습니다. 마찬가지로 접시는 한 선반에 최대 10개까지 놓을 수 있으므로, 필요한 선반의 최소 개수는 (sumq + 10 - 1) / 10으로 계산합니다.
분자에 5나 10을 미리 더해주는 이유는, 총개수가 5 또는 10보다 작은 경우에도 결과가 0이 아니라 최소 1이 되도록 보장하기 위해서입니다. 즉, 컵이나 접시가 하나라도 존재한다면 최소 한 개의 선반이 반드시 필요하기 때문입니다.
마지막으로 두 값을 더한 결과가 주어진 선반 개수 m보다 작거나 같으면 정리가 가능하므로 "Yes"를, 그렇지 않으면 "No"를 출력하면 됩니다.
C++ 구현 예제
// C++ 코드: 컵과 접시를 선반에
// 깔끔하게 정리할 수 있는지 확인
#include<bits/stdc++.h>
using namespace std;
// 정리 가능 여부를 검사하는 함수
void canArrange1(int p[], int q[], int m){
int sump = 0, sumq = 0;
// 컵의 총 개수 계산
for(int i = 0; i < 3; i++)
sump += p[i];
// 접시의 총 개수 계산
for(int i = 0; i < 3; i++)
sumq += q[i];
// 분자에 5와 10을 더하는 이유는,
// 총합이 5 또는 10보다 작아도
// 결과가 0이 아닌 1이 되도록 하기 위함
int mp = (sump + 5 - 1) / 5;
int mq = (sumq + 10 - 1) / 10;
if(mp + mq <= m)
cout << "Yes";
else
cout << "No";
}
// 드라이버 코드
int main(){
// 종류별 컵 개수
int p[] = {4, 3, 7};
// 종류별 접시 개수
int q[] = {5, 9, 10};
// 선반 개수
int m = 10;
// 함수 호출
canArrange1(p, q, m);
return 0;
}
실행 결과
Yes
복잡도 분석
컵과 접시의 종류 수를 n이라 할 때, 배열을 각각 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 별도의 추가 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)로 문제를 해결할 수 있습니다.