BOJ 5102 - Sarah's Toys

문제

BOJ 5102 - Sarah's Toys

Sarah가 A개의 장난감을 가지고 있고, 오빠(brother)가 B개를 가지고 있다. Sarah가 오빠보다 더 많은 장난감을 갖게 하려면, Sarah는 오빠에게 몇 개를 줄 수 있고 그래도 몇 개가 남는지를 구하는 문제이다.

Sarah가 오빠에게 k개를 주면, Sarah는 A-k개, 오빠는 B+k개를 가진다. Sarah가 오빠보다 더 많으려면 A - k > B + k 조건이 성립해야 한다. 즉, 최대로 줄 수 있는 k는 (A - B - 1) / 2이다. 단, A - B < 2면 줄 수 없다.

입력

• 여러 줄에 걸쳐 A B가 주어진다.
• 0 0이 입력되면 종료한다.

출력

각 케이스에 대해 Sarah가 줄 수 있는 최대 장난감 수와 그 후 남는 장난감 수를 출력한다.

예제

풀이

A와 B의 차이를 기반으로 분기 처리한다.

1. A, B를 입력받고, 0 0이면 종료한다.
2. diff = A - B를 계산한다.
3. diff < 2이면 줄 수 없으므로 0 0을 출력한다.
4. diff가 홀수이면 최대로 줄 수 있는 수는 (diff - 3) / 2, 남는 수는 1이다.
5. diff가 짝수이면 최대로 줄 수 있는 수는 diff / 2, 남는 수는 0이다.

핵심 아이디어: A - k > B + k 에서 A - B > 2k이므로 k < (A - B) / 2이다. diff가 홀수일 때는 (diff - 1) / 2 - 1 = (diff - 3) / 2가 최댓값이 되고, 짝수일 때는 diff / 2 - 1이 최댓값이 된다. 코드에서는 이 두 경우를 정수 나눗셈으로 간결하게 처리한다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  while (1)
  {
    int a, b, diff;
    cin >> a >> b;
    if (!a && !b)
      break;
    diff = a - b;
    if (diff < 2)
      cout << 0 << ' ' << 0;
    else if (diff % 2)
      cout << (diff - 3) / 2 << ' ' << 1;
    else
      cout << diff / 2 << ' ' << 0;
    cout << '\n';
  }
}

복잡도

• 시간: O(N) — 입력 케이스 수 N만큼 처리 (각 케이스는 O(1))
• 공간: O(1) — 상수 개의 변수만 사용