BOJ 24040 - 예쁜 케이크

문제 링크

문제#

Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. $N$ 명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다.

여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 케이크를 의미한다.

• 케이크는 높이가 $1$이고, 부피가 $N$인 직육면체 모양이다.
• 케이크를 적절히 칼질해서 한 변의 길이가 $1$인 정육면체 모양 조각 $N$ 개로 나눌 수 있어야 한다.
• 케이크의 옆면에 가로 너비가 $1$인 직사각형을 이어 붙여 만든 띠를 딱 맞게 두를 수 있어야 한다.
• 장식용 띠는 가로 폭이 $1$인 빨간색, 초록색, 하얀색 직사각형이 순서대로 번갈아 가면서 같은 개수만큼 나와야 한다.

예를 들어, 아래 그림은 $N = 8$인 경우의 예쁜 케이크 중 하나와 그에 사용된 띠를 나타낸다.

아쉽게도 $N$이 얼마인지에 따라 예쁜 케이크를 만들지 못 할 수도 있다. 종서의 친구들을 위해 부피가 $N$인 예쁜 케이크를 만들 수 있는지 알려주자.

입력#

첫 번째 줄에 전체 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다.

이후 $T$ 개의 줄에 각각 문제에서 언급한 정수 $N$이 한 줄에 하나씩 주어진다.

출력#

$T$ 개의 줄에 걸쳐 한 줄에 하나씩 문제의 답을 출력해야 한다.

부피가 $N$인 예쁜 케이크를 만들 수 있으면 TAK, 아니면 NIE를 출력한다.

풀이#

이 문제는 케이크 모양을 실제로 구성해 보는 문제가 아니라, 가능한 경우가 어떤 수론적 조건으로 떨어지는지를 관찰하는 문제다. 현재 코드는 그 결과를 그대로 사용해 (N - 2) % 3 == 0이거나 N % 9 == 0이면 TAK, 아니면 NIE를 출력한다.

즉 핵심은 긴 시뮬레이션이 아니라 판정식을 찾아내는 데 있다. 관찰이 끝난 뒤의 구현 자체는 입력마다 조건문 한 번으로 끝날 만큼 짧다.

코드#

#include <iostream>
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
 
	long long N;
	for (int i = 0; i < T; i++) {
		cin >> N;
 
		if((N - 2) % 3 == 0 || N % 9 == 0)
			cout << "TAK" << '\n';
		else
			cout << "NIE" << '\n';
 
	}
	return 0;
}

복잡도#

• 시간 복잡도: 각 테스트 케이스를 상수 시간 조건식으로 판정하므로 $O(T)$이다.
• 공간 복잡도: 추가 자료구조 없이 판정하므로 $O(1)$이다.

마무리#

이 문제는 케이크 모양을 실제로 구성해 보는 문제가 아니라, 가능한 경우가 어떤 수론적 조건으로 떨어지는지를 관찰하는 문제다.