백준 27952번 [보디빌딩](C++) -yes6686- 티스토리

백준 문제 풀이: 27952 [보디빌딩]

---

문제 링크: https://www.acmicpc.net/problem/27952

문제 설명:

n개의 운동 루틴에 대해 필요한 보충제와 제공 가능한 보충제의 양이 주어집니다. 모든 운동 루틴이 끝날 때까지 보충제를 충분히 제공할 수 있는지 확인하고, 추가적으로 남는 보충제를 활용하여 x개의 추가 운동 루틴을 몇 번 더 수행할 수 있는지 계산합니다.

다음 조건을 만족해야 합니다:

• 각 운동 루틴에서 필요한 보충제의 총량이 현재까지 제공된 보충제의 누적합보다 작거나 같아야 합니다.
• 모든 운동이 끝난 뒤 남는 보충제를 x로 나누어 추가 운동 가능한 횟수를 계산합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

long long int arr1[500001]; // 각 운동 루틴의 필요한 보충제 양
long long int arr2[500001]; // 각 운동 루틴의 제공 가능한 보충제 양

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long int n, x;
    cin >> n >> x; // 운동 루틴 수와 추가 운동당 필요한 보충제 양

    for (int i = 0; i < n; i++) {
        cin >> arr1[i]; // 각 루틴에서 필요한 보충제 양 입력
    }

    long long int sum = 0; // 제공된 보충제의 누적합
    for (int i = 0; i < n; i++) {
        cin >> arr2[i]; // 각 루틴에서 제공 가능한 보충제 양 입력
        sum += arr2[i]; // 누적합 갱신

        if (sum < arr1[i]) {
            // 보충제가 부족한 경우
            cout << -1;
            return 0;
        }
    }

    // 남은 보충제를 추가 운동 횟수로 계산
    cout << (sum - arr1[n - 1]) / x;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 보충제 누적합을 관리하며 필요한 보충제 양과 비교해 운동 루틴을 수행 가능한지 확인합니다.
  • 모든 운동 루틴이 완료된 이후, 남은 보충제 양을 이용해 추가 운동 횟수를 계산합니다.
• 구현 세부사항:
  • 첫 번째 배열 arr1는 각 루틴에서 필요한 보충제 양을 저장합니다.
  • 두 번째 배열 arr2는 각 루틴에서 제공 가능한 보충제 양을 저장하며, 이를 누적합 sum으로 관리합니다.
  • 누적합 sum이 각 루틴의 요구량보다 작아지는 순간, 조건이 깨지므로 -1을 출력하고 종료합니다.
  • 모든 루틴이 정상적으로 끝난 후, 남은 보충제에서 마지막 루틴의 필요 보충제를 제외한 값을 x로 나누어 추가 운동 횟수를 계산합니다.
• 시간 복잡도 분석:
  • 배열을 한 번 순회하며 입력을 받고, 두 번째 순회에서 누적합을 계산하므로 O(n)입니다.
  • 전체 복잡도는 O(n)으로 매우 효율적입니다.

---

결과

입력된 보충제 정보와 추가 운동당 필요한 보충제 양에 따라 정상적인 운동 수행 가능 여부와 추가 운동 가능한 횟수를 정확히 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!