백준 23814번 [아 저는 볶음밥이요](C++) -yes6686- 티스토리

백준 문제 풀이: 23814 (아 저는 볶음밥이요)

---

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

문제 설명:

볶음밥을 만드는 데 사용할 세 가지 재료의 수량(n, m, k)이 주어집니다. 한 접시의 볶음밥을 만들기 위해서는 정확히 d개씩의 재료가 필요합니다. 최대한 많은 접시의 볶음밥을 만들고, 남은 재료의 수량 k를 출력하세요. 재료의 수량을 조정할 때, 추가적인 재료를 사용할 수 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    long long int d; // 필요한 재료의 개수
    cin >> d;
    long long int n, m, k; // 세 가지 재료의 수량
    cin >> n >> m >> k;

    // 최대 볶음밥 접시 수
    long long int maxMandoCnt = (n + m + k) / d;

    // 재료를 조정하여 최대 접시 수에 맞추기
    while (true) {
        // 현재 가능한 접시 수 계산
        if ((n / d + m / d + k / d) == maxMandoCnt) break;

        // 부족한 재료를 조정
        if (n % d > m % d) { 
            // n의 부족분을 k에서 보충
            k -= (d - (n % d));
            n += (d - (n % d));
        } else { 
            // m의 부족분을 k에서 보충
            k -= (d - (m % d));
            m += (d - (m % d));
        }
    }

    // 남은 재료 출력
    cout << k << '\n';
    return 0;
}

---

코드 설명

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

• 핵심 알고리즘: 최대 볶음밥 접시 수를 계산하고, 부족한 재료의 수를 추가 재료 k에서 보충하여 목표 접시 수를 달성합니다.
• 구현 세부사항:
  • (n + m + k) / d: 재료를 모두 합한 후 필요한 개수 d로 나눠 최대 접시 수를 계산합니다.
  • 부족한 재료의 수는 n % d 또는 m % d로 계산하고, 이를 k에서 보충합니다.
  • 재료를 조정한 후, 목표 접시 수에 도달했는지 확인하며 루프를 종료합니다.
• 시간 복잡도 분석:
  • 재료의 조정은 최대 O(n) 번 수행될 수 있습니다.
  • 루프 내의 연산은 O(1)이므로 전체 시간 복잡도는 O(n)입니다.

---

결과

최대 볶음밥 접시 수를 만들고 남은 재료 k의 값을 정확히 계산하여 출력합니다.

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