문제 개요
배열 p에는 세 가지 종류의 컵이, 배열 q에는 세 가지 종류의 접시가 담겨 있고, 사용할 수 있는 선반의 개수는 m개라고 가정해 봅시다. 이때 주어진 조건을 만족하도록 컵과 접시를 선반에 깔끔하게 정리할 수 있는지 확인하는 것이 이번 글의 목표입니다.
깔끔한 정리를 위한 조건
컵과 접시의 배치가 '깔끔하다'고 판단하려면 다음 세 가지 조건을 모두 충족해야 합니다.
- 하나의 선반에는 컵과 접시를 함께 둘 수 없습니다.
- 하나의 선반에는 최대 5개의 컵만 놓을 수 있습니다.
- 하나의 선반에는 최대 10개의 접시만 놓을 수 있습니다.
예제로 이해하기
입력이 p = [4, 3, 7], q = [5, 9, 10], m = 11이라고 해 보겠습니다.
- 컵의 총 개수는 14개이므로, 선반 하나당 최대 5개씩 담으려면 3개의 선반이 필요합니다.
- 접시의 총 개수는 24개이므로, 선반 하나당 최대 10개씩 담으려면 역시 3개의 선반이 필요합니다.
- 따라서 필요한 전체 선반 수는 3 + 3 = 6개이며, 이는 주어진 선반 수 11보다 작습니다.
결과적으로 필요한 선반이 충분하므로 출력은 True가 됩니다.
풀이 접근 방법
이 문제는 간단한 산술 계산만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 컵의 총합
sum_p와 접시의 총합sum_q를 각각 구합니다. - 필요한 컵 전용 선반 수
m_p는 총 컵 수를 5로 나눈 값의 올림입니다. - 필요한 접시 전용 선반 수
m_q는 총 접시 수를 10으로 나눈 값의 올림입니다. m_p + m_q <= m이라면True, 그렇지 않으면False를 반환합니다.
여기서 올림 나눗셈은 정수 나눗셈을 활용해 (합계 + 나누는 수 - 1) // 나누는 수 형태로 깔끔하게 구현할 수 있습니다.
파이썬 구현 코드
def is_valid(p, q, m):
sum_p = 0
sum_q = 0
# 컵의 총 개수 계산
for i in range(len(p)):
sum_p += p[i]
# 접시의 총 개수 계산
for i in range(len(q)):
sum_q += q[i]
# 올림 나눗셈으로 필요한 선반 수 계산
m_p = (sum_p + 5 - 1) // 5 # 컵용 선반 (선반당 최대 5개)
m_q = (sum_q + 10 - 1) // 10 # 접시용 선반 (선반당 최대 10개)
if m_p + m_q <= m:
return True
else:
return False
p = [4, 3, 7]
q = [5, 9, 10]
m = 11
print(is_valid(p, q, m))입력
[4, 3, 7], [5, 9, 10], 11
출력
True
마무리
이 문제의 시간 복잡도는 두 배열을 한 번씩 순회하므로 O(n + m)이며, 공간 복잡도는 O(1)로 매우 효율적입니다. 올림 나눗셈 공식만 기억해 두면 비슷한 유형의 '자원 분배' 문제(예: 버스 좌석 배정, 상자 포장 등)에서도 동일한 패턴으로 손쉽게 해결할 수 있습니다.