백준 24040 (예쁜 케이크) c++

문제

24040번: 예쁜 케이크

직사각형 넓이 n(가로 * 세로)이 주어지면 가로 길이가 각각 1인 세가지 색상 천으로 딱 맞아 떨어지게 포장할 수 있는지 구하는 문제 입니다.

예를 들어 넓이 n이 8이면 (2 * 4) 둘레는 12이므로 세가지 색상천의 길이 3으로 나누어 떨어지므로 포장가능합니다.

 

 따라서 우리는 직사각형의 둘레의 길이가 3의 배수인것을 알 수 있습니다.

가로의 길이는 3a + x

세로의 길이는 3b + y 로 설정해 놓았습니다.

따라서 3a + x + 3b + y가 3의 배수가 되어야 하므로 

3a와 3b는 이미 3의 배수이고 3의 배수끼리 더해도 3의 배수를 만족합니다.

그러므로 x+y가 3의 배수가 되어야 합니다. 

(0, 0), (1, 2), (2, 1) 이면 가능합니다.

 

 

이제 n(넓이)이 입력으로 들어올때를 체크해야합니다.

n = (3a + x)(3b + y) = 9ab + 3ay + 3bx + xy 입니다.

 

1) 먼저 x, y 에대해서 (0, 0)을 대입하면 n = 9ab가 나옵니다. 

따라서 n이 일단은 9의 배수가 되어야 한다는 사실을 알 수 있습니다.

 

2) 그 다음 x, y에 대해서 (1, 2) 또는 (2, 1)을 대입하면 n = 9ab + 3a + 6b + 2가 나옵니다.

여기서 묶어주면 n = 3(3ab + a + 2b) + 2 가 되는데 중요한 사실은 n이 3의 배수보다 2가 크다는 사실을 알 수 있습니다.

 

1)과 2)를 종합해주면 n은 9의 배수 또는 3의 배수에서 2를 더한 값이 되어야합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        ull n;
        cin >> n;
        if (n % 9 == 0 || n % 3 == 2)
            cout << "TAK" << '\n';
        else cout << "NIE" << '\n';
    }
    
 
    return 0;
}