문제 개요
A유형 항목 N개와 B유형 항목 M개가 주어졌을 때, 만들 수 있는 크기 3짜리 그룹의 최대 개수를 구하는 것이 이번 문제의 목표입니다.
단, 하나의 그룹에는 두 유형의 항목이 각각 최소 한 개씩 포함되어야 합니다. 즉, 모든 그룹은 A유형과 B유형의 항목을 반드시 하나 이상씩 가져야 합니다.
예제로 이해하기
먼저 예제를 통해 문제를 살펴보겠습니다.
입력 − N = 3, M = 5
출력 − 2
설명
그룹 1: A유형 1개 + B유형 2개
그룹 2: A유형 1개 + B유형 2개
총 A유형 2개와 B유형 4개가 사용됩니다.
다른 예제도 확인해 보겠습니다.
입력 − N = 5, M = 9
출력 − 4
접근 방법
이 문제는 다음 네 가지 경우로 나누어 해결할 수 있습니다.
경우 1 − M ≥ 2N일 때, 만들 수 있는 최대 그룹 수는 M입니다.
경우 2 − N ≥ 2M일 때, 만들 수 있는 최대 그룹 수는 N입니다.
경우 3 − (M+N) % 3 == 0일 때, 만들 수 있는 최대 그룹 수는 (M+N)/3입니다.
경우 4 − 위의 어느 조건에도 해당하지 않으면, 최대 그룹 수는 (M+N)/3에 남은 그룹 여부를 반영한 값이 됩니다.
남은 그룹이 있는지 확인하려면 먼저 N = N % 3, M = M % 3으로 설정해 두 유형의 남은 항목 수를 구한 뒤, 다음 조건을 검사합니다.
N ≠ 0 && M ≠ 0 && (N + M) ≥ 3
이 조건이 참이면 최종 결과에 1을 더합니다.
알고리즘 동작 순서
- MaxGrp() 함수에서는 if 조건문을 사용해 위의 경우들을 순서대로 확인합니다.
- M ≥ 2*N이 참이면 M을 답으로 반환하고, 그렇지 않은 상태에서 N ≥ 2*M이 참이면 N을 답으로 반환합니다.
- 두 조건이 모두 거짓이면 (M+N) % 3 == 0인지 검사하고, 참이라면 (M+N)/3을 답으로 반환합니다.
- 모든 조건이 거짓이라면 int형 변수 count를 (M+N)/3 값으로 초기화합니다. 이후 N = N % 3, M = M % 3으로 설정하고 앞서 설명한 조건으로 남은 그룹이 있는지 확인한 뒤, 조건이 참이면 count에 1을 더해 반환합니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 위에서 설명한 단계를 구현합니다.
int MaxGrp(int N, int M){
if (N >= 2 * M)
return N;
if (M >= 2 * N)
return M;
if ((M + N) % 3 == 0)
return (M + N)/3;
int count = (M + N)/3;
M %= 3;
N %= 3;
if (M && N && (M + N) >= 3)
count++;
return count;
}
int main(){
int N = 5, M = 9;
cout << MaxGrp(N, M);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
4