[백준/C++/Gold(5)] 27087 - 직육면체

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

27087번: 직육면체

본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.

 

 이번에도 기하학 문제를 풀어보려고 했는데, 문제 이름을 보고 기하학 같아서 풀었는데 알고 보니 그냥 정수론 문제였다. 

직육면체~

문제는 이렇다 : 

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

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

 

생각 : 

 일단 딱 보고 드는 생각은 없어서 차근차근 "뭐가 최적의 전략일까?"를 고민했다. 우선 당연한 것 몇가지를 생각해보려고 했다. 

 

1. 어느 구석부터 차곡차곡 채워야한다. 그렇지 않고 $p$ 미만의 거리를 띄운채로 채우기 시작하면 나중에 채울 방법이 너무 복잡해지고, 채울 수도 없게 될 가능성이 크다.

 

2. a, b, c 중 적어도 2개의 값은 p보다 크거나 같아야 한다. 안그러면 들어갈 공간 조차 없다.

 

... 여기서 한동안 막혔었는데, 우선 $a \le b \le c$로 정렬을 했다고 생각하고 풀어보기로 했다. 여기서 우리는 3가지 방법으로 해당 직육면체를 채울 수 있다.

 

1. $1 \times p \times p$  모양으로 우선 $ b \times c $ 부터 채우기 시작하는 것.

2. $p \times 1 \times p$  모양으로 우선 $ a \times c $ 부터 채우기 시작하는 것.

3. $p \times p \times 1$  모양으로 우선 $ a \times b $ 부터 채우기 시작하는 것.

 

중요한건 1, 2, 3을 전부 만족시킬 필요는 없고 어느 하나라도 채워지면 되는 것이다.

 

1. $1 \times p \times p$  모양으로 우선 $ b \times c $ 부터 채우기 시작한다고 생각하면,

b와 c는 둘다 p로 나누어 떨어져야 할 것이다. 그렇지 않으면 빈공간이 생겨서 전부 채우지 못하게 된다.

 

2. $p \times 1 \times p$  모양으로 우선 $ a \times c $ 부터 채우기 시작한다고 생각하면,

a와 c는 둘다 p로 나누어 떨어져야 할 것이다. 그렇지 않으면 빈공간이 생겨서 전부 채우지 못하게 된다.

 

3. $p \times p \times 1$  모양으로 우선 $ a \times b $ 부터 채우기 시작한다고 생각하면,

a와 b는 둘다 p로 나누어 떨어져야 할 것이다. 그렇지 않으면 빈공간이 생겨서 전부 채우지 못하게 된다.

 

그럼 결론적으로, a, b, c가 p로 나누어 떨어지는 지를 검사해서, 그 개수가 2개 이상이면 채우는게 가능해진다... 라는 뜻이다.이게 이렇게 간단하게 되는게 말이 안된다고 생각해서 일단 테스트를 해봤다.

코드 :

#include <iostream>

using namespace std;

int main()
{
    int t;
    cin >> t;

    while(t--){
        int a, b, c, p, count = 0;
        cin >> a >> b >> c >> p;
        count += (!(a % p) ? 1 : 0);
        count += (!(b % p) ? 1 : 0);
        count += (!(c % p) ? 1 : 0);
        if(count >= 2){
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }

    return 0;
}

 

이를 제출 했는데 :

 

이게 되네...

 

나 같은 경우는 정수론도 정수론... 이지만 구성적인 문제로 접근해서 풀었다고 생각도 든다.