BOJ 1980 - 햄버거 사랑

문제

BOJ 1980 - 햄버거 사랑

햄버거 패티는 두 종류(크기 n, m)가 있고, 콜라는 크기 1이다. 총 t개의 식품을 구입할 때 햄버거(패티 조합) 최대 개수와 그때 콜라 개수를 구하는 문제이다. 햄버거 1개는 패티 n개 또는 m개로 구성되고, 나머지는 콜라로 채운다.

입력

첫째 줄에 패티 크기 n, m과 총 식품 수 t가 주어진다.

출력

햄버거 최대 개수와 그때의 콜라 개수를 공백으로 구분하여 출력한다.

예제

풀이

콜라 개수를 0부터 t까지 브루트포스로 시도하며 나머지 패티로 햄버거를 최대로 만들 수 있는 경우를 탐색한다.

1. t < min(n, m)이면 패티를 하나도 구성할 수 없으므로 햄버거 0개, 콜라 t개를 출력하고 종료한다.
2. 콜라 수 coke를 0부터 t-1까지 순회하며 남은 패티 수 i = t - coke를 결정한다.
3. 큰 패티 수 mx로 나누는 가능한 조합 j(0 ~ i/mx)를 탐색한다.
4. 큰 패티 j개를 사용하고 남은 tmp = i - j*mx가 작은 패티 크기 mn의 배수이면 햄버거 개수를 계산하고 출력한다.
5. 가장 먼저 찾은 경우(콜라가 가장 적은 경우)가 햄버거 최대 경우이다.

핵심 아이디어: 콜라를 최소화하는 순서로 탐색하면 자연스럽게 햄버거 최대 경우를 먼저 발견할 수 있다. 이중 반복문으로 큰 패티와 작은 패티의 조합을 완전 탐색한다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
  int n, m, t;
  cin >> n >> m >> t;
  int mx = max(n, m), mn = min(n, m);
 
  if (t < mn)
  {
    cout << 0 << ' ' << t << '\n';
  }
  for (int i = t; i > 0; i--)
  {
    int coke = t - i;
    for (int j = 0; j <= (i / mx); j++)
    {
      int tmp = i - (j * mx);
      if (tmp % mn == 0)
      {
        int bg = (tmp / mn) + j;
        cout << bg << ' ' << coke << '\n';
        return 0;
      }
    }
  }
}

복잡도

• 시간: O(T^2 / max(n,m)) (이중 반복, 최악의 경우 T^2에 수렴)
• 공간: O(1)