BOJ 27087 - 직육면체 (Python3)

문제를 풀고 기여를 할 때마다 생각하는 것인데, 수학적으로 자명해 보이는 것이 실제로 그다지 자명하지 않은 경우 기여 편차는 하늘과 땅으로 갈린다.

내 눈에는 증명이 바로 보이지만 남의 눈에는 증명이 아예 안 보이는 경우가 많나 보다.

이 문제는 어제 개최된 SciOI 2022의 D번 문제이다. 개인적으로는 총 10개의 문제 중 가장 쉬웠다. 발상 난이도가 골드라는 건 절대 동의할 수 없다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

A×B×C 모양의 직육면체를 1×p×p 모양의 직육면체로 채울 수 있는지 판별하시오. 단, p는 소수이다.

직육면체의 방향은 중요하지 않다. 즉, 직육면체를 돌려서 p×1×p, p×p×1로 채우는 것도 가능하다.

 

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

이후 한 줄에 하나씩 테스트 케이스에 대한 정보가 주어진다. 각 테스트 케이스는 A, B, C, p가 띄어쓰기를 사이에 두고 주어진다.

제한은 다음과 같다.

\(1\le T\le 1000, 1\le A,B,C \le 100, 2\le p\le 97, p\)는 소수.

 

예제 입력)

3
1 1 1 2
1 1 4 2
2 2 2 2

 

출력

각각의 테스트 케이스에 대해 직육면체를 채울 수 있으면 1, 없으면 0을 출력한다. 한 줄에 하나씩 출력한다.

 

예제 출력)

0
0
1

 

---

내 코드

for _ in range(int(input())):
    a,b,c,p = map(int,input().split()); ans = 0
    for i in (a,b,c):
        if i%p == 0: ans += 1
    print(1 if ans > 1 else 0)

 

각각의 테스트 케이스에 대해서, 직육면체를 채울 수 있는 경우는 어떤 경우일까?

당연히 부피는 p²의 배수여야 할 것이다. 낱개 직육면체 하나의 부피가 p²이기 때문이므로. 그렇단 이야기는 세 모서리 중 적어도 하나는 p의 배수여야 한다는 소리다.

 

p의 배수가 세 모서리 중 2개 이상이면 당연한 방법으로 채울 수 있다. A=ap, B=bp라고 두면, A×B 면에다가 낱개 직육면체를 넓게 펼친 다음 그걸 C번 반복하면 채울 수 있으니.

그리고 p의 배수가 세 모서리 중 0개라면 당연히 채울 수 없고. 그럼 관건이 되는 것은 p의 배수가 세 모서리 중 하나만일 때다.

직관으로는 채워지지 않을 것이라고 생각이 들 테지만, 그래서야 proof by AC일 뿐이고 엄밀한 증명이 아니다.

 

만약 A, B가 p의 배수가 아니라고 하자. 직육면체의 겉인 A×B면에 닿는 낱개 직육면체의 면은 당연히 넓이가 p이거나 p²일 것이다. 낱개 직육면체의 면 넓이는 p가 아니면 p²일 테니 말이다.

그렇다면 A×B의 넓이가 p의 배수가 되어야 한다. 그것은 전제에 모순이므로, A×B×C 직육면체는 1×p×p 작은 직육면체로 채워지지 않게 된다.

그러면? 이제부터 할 일은 간단하다. p의 배수 길이를 가진 모서리의 길이를 세고, 그 수가 2개 이상인지 판단한 다음 조건에 따라 0과 1을 출력하면 끝이다.

 

이로서 27087번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.