[백준/C++] 4030번 포켓볼

4030번: 포켓볼

풀이

백준 알고리즘 분류가 이분 탐색으로 되어 있지만 이분 탐색을 사용하지 않아도 되는 문제이다. 삼각형과 사각형을 만들 수 있는 수식을 찾아 풀 수 있다.

삼각형을 만들 수 있는 공의 개수는 다음과 같다.

삼각형 한변의 길이	1	2	3	4	5	6	i
공의 개수 (x)	1*(1+1)/2 = 1	2*(2+1)/2=3	3*(3+1)/2= 6	4*(4+1)/2= 10	5*(5+1)/2= 15	6*(6+1)/2= 21	i*(i+1)/2

위의 과정에서 삼각형을 만들 수 있는 공 x개를 구할 수 있다. 이때 x+1개의 공으로 정사각형 트레이에 넣을 수 있는지 확인한다. 이 또한 공식을 구할 수 있다.

x+1	2	3	4	...	9	...	16
x+1을 담을 수 있는 사각형 트레이에 넣을 수 있는 최대 공의 개수 = $(int)\sqrt(x+1) * (int)\sqrt(x+1)$	$(int)\sqrt(2) * (int)\sqrt(2)=1*1=1$	$(int)\sqrt(3) * (int)\sqrt(3)=1*1=1$	$(int)\sqrt(4) * (int)\sqrt(4)=2*2=4$	4	$(int)\sqrt(9) * (int)\sqrt(9)=3*3=9$	9	$(int)\sqrt(16) * (int)\sqrt(16)=4*4=16$

x+1과 $(int)\sqrt(x+1) * (int)\sqrt(x+1)$이 같을 때 정사각형 트레이에 모든 공을 넣을 수 있다. 이 경우 x개로 삼각형을 만들 수 있고, x+1개로 사각형을 만들 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n = 0;
  while (++n)
  {
    int a, b, count = 0, tri = 0, squ = 0;
    cin >> a >> b;

    if (a == 0 && b == 0)
      break;

		// 544721 = 문제에서 주어진 범위 내에서 삼각형을 만들 수 있는 최대 공의 개수
    for (int i = 2; i <= 44721; i++)
    {
      tri = i * (i + 1) / 2;
      if (tri > a - 1)
      {
        if (tri >= b - 1)
          break;

        squ = tri + 1;
        if (squ == (int)sqrt(squ) * (int)sqrt(squ))
          count++;
      }
    }
    cout << "Case " << n << ": " << count << "\n";
  }
  return 0;
}