C++로 배터리 조합 수 구하기: 기기 사용 횟수에 따른 계산 방법

문제 개요

최대 5번까지 사용할 수 있는 배터리 n개가 있다고 가정해 봅시다. 배터리 3개가 필요한 기기들이 있으며, 기기를 한 번 사용할 때마다 사용된 배터리의 사용 횟수가 1씩 증가합니다. 기기를 k번 사용해야 한다면, 이를 구동하기 위해 만들 수 있는 배터리 조합이 몇 개인지 구해야 합니다.

단, 하나의 배터리는 두 개의 기기에서 동시에 사용될 수 없으며, 이미 5번 사용된 배터리는 더 이상 포함될 수 없습니다. 각 배터리의 현재 사용 횟수는 배열 batt에 주어집니다.

예를 들어 입력이 n = 6, k = 2, batt = {2, 4, 4, 2, 1, 3}이라면 출력은 1이 됩니다. 즉, 기기를 k번 구동하기 위해 만들 수 있는 배터리 조합은 단 하나뿐입니다.

해결 접근 방식

이 문제는 다음과 같은 논리로 해결할 수 있습니다.

• 각 배터리마다 현재 사용 횟수에 앞으로 사용할 횟수 k를 더했을 때 5 이하인지 확인합니다.
• 조건을 만족하는 배터리의 개수를 셉니다.
• 하나의 기기를 구동하려면 배터리 3개가 필요하므로, 전체 개수를 3으로 나눈 값이 곧 만들 수 있는 조합의 수입니다.

알고리즘 의사 코드

ans := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    if batt[i] + k <= 5, then:
        (increase ans by 1)
return ans / 3

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(int n, int k, int batt[]) {
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(batt[i] + k <= 5)
            ans++;
    }
    return ans / 3;
}
int main() {
    int n = 6, k = 2, batt[] = {2, 4, 4, 2, 1, 3};
    cout<< solve(n, k, batt);
    return 0;
}

입력

6, 2, {2, 4, 4, 2, 1, 3}

출력

1

코드 설명

solve 함수는 배열을 한 번 순회하면서 각 배터리가 추가로 k번 더 사용될 수 있는지(사용 횟수 + k ≤ 5) 판단합니다. 조건을 만족하는 배터리만 카운트한 뒤, 기기 하나당 배터리 3개가 필요하므로 최종적으로 3으로 나누어 정수 나눗셈 결과를 반환합니다.

예제 입력의 경우 사용 가능한 배터리는 {2, 4, 4, 2, 1, 3} 중 3개(2, 2, 1 또는 3 등 조건을 만족하는 값들)이며, 이를 통해 정확히 1개의 조합을 만들 수 있으므로 출력은 1입니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 배열을 한 번만 순회하기 때문에 매우 효율적입니다.