[백준][C++] 23570번 Grid Triangle (math)

1. 문제

https://www.acmicpc.net/problem/23570

23570번: Grid Triangle

2. 한 집합에서의 모든 경우의 수

- 삼각형의 세 좌표가 다음과 같을 때

- (0, 0, 0) , (x, y, z), (xx, yy, zz)

- 차이들은 다음과 같다.

• p1 : x, y, z         
• p2 : xx, yy, zz
• d : x - xx, y - yy, z - zz

문제에서 주어진 조건

- 숫자들의 절댓값의 집합은 같아야한다. (또한 cuboid 이므로 0이 와서는 안된다.)

- 서로 다른 숫자들이다.

- 각 축의 값들의 절댓값들은 같아서는 안된다.

---- 예를들어 같은 축인 |z| 와 |zz|가 같은 경우, z - zz 는 z*2 나 0 의 꼴의 형태가 나오게 된다.

---- |x| 나 |y| 값이랑 다른 값이 나오게되므로 이는 잘못되었고, 0이 나오면 안된다.

---- 만약 x 가z*2 라도, z가 계산으로 나와야하니 y 가 z값이 되어버리며, 이는 같아서는 안된다는 조건을 위반한다.

 

 

-  조건에 의하여 |x| 와 |y|, |z| 에 특정한 크기를 부여할 수 있다. 

-  |z| 값이 가장 크다고 가정하면

- 한 축에서 |x| 와 |y| 로 |z| 를 만들어야하니 |x| + |y| = |z| 이 성립한다는 것을 알 수 있다.

- 이제 위 식을 고쳐 쓸 수 있다.

• p1 : x, y, z
• p2 : -y, z, x
• d  : z, -x, y

- 이제 이러한 모든 경우의 수를 구해보면

- 부호의 경우의 수 2*2*2 = 8

- x, y, z 의 순열 3! = *6 

- p2 와 d 의 교환 = *2

- p1 과 p2 의 중복 = /2

- 그러므로 제약이 없을경우 한 |x|, |y|, |z|, 집합에 대해 총 48 가지의 경우의 수가 생기는 것을 알 수 있다.

 

- 여기서 예제 3 3 3 의 답이 48 인 이유를 알 수 있다. - 제약이 3 3 3 일 경우 1 2 3 이 유일한 집합이기 때문.

 

 

3. 제약이 있을 경우1 : 123 ~ AAA

- 문제에선 x 축, y축, z축에 대한 제약을 주었다.

- 일단 이들을 정렬한후,

- A < B < C 로 만들어

- 제약이 A A A 인 경우를 먼저 해결할 수 있다.

- 이 경우 |a| + |b| = |c| 를 만족하면서 |a| != |b| 인 모든 경우의 수를 구하여 48을 구하면된다.

- 이 때 |c| <= A 이다.

int f1(int z)
{
    return z / 2 - ((z % 2) ? 0 : 1);
}

 

3. 제약이 있을 경우2 : 12(A+1) ~ ABB

• p1 : a, b, c
• p2 : -b, c, a
• d  : c, -a, b

- p1 식과 p2 식에 의해

- |a|와 |b| 는 |A| 보다 작거나 같아야하고

- |c| 는 |B| 보다 작거나 같아야한다. (b는 자연적으로 A보다 작거나 같아야함)

- 또한 c 는 A 보다 커야한다(작거나 같은 경우는 2번에서 계산됨)

 

- 이때 a와 b는 자리를 바꿀 수 있지만 c는 고정이므로

- 부호의 경우의 수 : 8

- a 와 b의 순서 : *2

- 한 집합에 총 16가지의 경우의 수가 생기는 것을 알 수 있다.

int f2(int z)
{
    int sub1 = z - xyz[0] - 1;
    int ret = f1(z) - sub1;
    return (ret >= 0) ? ret : 0;
}

 

4. 전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int xyz[3];

int f1(int z)
{
    return z / 2 - ((z % 2) ? 0 : 1);
}
int f2(int z)
{
    int sub1 = z - xyz[0] - 1;
    int ret = f1(z) - sub1;
    return (ret >= 0) ? ret : 0;
}
int main()
{
    cin >> xyz[0] >> xyz[1] >> xyz[2];
    sort(xyz, xyz + 3);
    long long answer = 0ll;
    for (int i = 3; i <= xyz[0]; i++)
    {
        answer += static_cast<long long>(f1(i) * 48);
    }
    for (int i = xyz[0] + 1; i <= xyz[1]; i++)
    {
        answer += static_cast<long long>(f2(i) * 16);
    }
    cout << answer << "\n";
}