[백준]24040번 예쁜케이크 - C/C++

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

24040번: 예쁜 케이크

문제

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

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

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

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

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

입력

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

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

출력

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

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

제한

•  1≤T≤1000  
•  1≤N≤10^18  
• 입력으로 주어지는 모든 수는 정수다.

---

장식용 띠의 갯수가 3가지 색상이 반복되므로 N=a*b 라고 할 때 둘레의 길이 : 2(a+b) 가 3의 배수이면 예쁜 케이크를 만들 수 있다. 이때 a*b를 직접 찾게 된다면 아무리 적게 돌아도 되지 않는 경우라면 루트N 번을 돌아야 한다. 그러므로 총 10^9 번을 돌아야하는데 이러한 입력이 1000개까지 들어올 수 있으니 10^12까지 시간이 걸릴 수 있는데 이는 시간제한인 1초에 턱없이 모자란 시간이다. 그러므로 다른 방법을 사용해야한다.

우선 가로의 길이를 3*a + x 라고 하고 세로의 길이를 3*b + y (x,y는 3으로 나누었을 때 나머지 즉, 0<= x,y < 3)라고 할때 넓이 N = (3a + x) * (3b + y) = 9ab + 3axy + 3bxy + xy 가 된다. 이 때 둘레의 길이가 3의 배수가 되려면 3a + 3b + x + y 가  3의 배수여야 하므로 x =  y =0 혹은 x,y=(1,2) or (2,1) 이여야 한다.

x= y = 0 인경우 N = 9*a*b 가 되므로 N이 9의 배수인 경우

x 와 y 가 1 , 2 인 경우는 N = 3(...) + 2  가 되므로 3으로 나누었을 때 나머지가 2인 경우로 나눌 수 있다.

#include <iostream>

using namespace std;

int T;
long long N;

void solve() {
	if ((N % 9) == 0) cout << "TAK\n";
	else if ((N % 3) == 2) cout << "TAK\n";
	else cout << "NIE\n";
	return;
}
int main() {
	cin >> T;
	while (T--) {
		cin >> N;
		solve();
	}
	return 0;
}

---

계절학기를 같이 듣는 친구와 공부를 같이하고 마무리로 그 친구가 듣는 알고리즘 캠프의 문제를 같이 풀기로 했다. 처음에 문제를 봤을때 길이랑 넓이를 이용해서만 풀면 될 줄 알았다. 그래서 풀었는데 시간초과가 떴다. 생각해보니 위에서 말한 것 처럼 문제의 시간에 맞지 않는 풀이여서 한참 고민하던 중 도저히 모르겠어서 친구의 도움을 받아 문제를 풀게 되었다. 이런 정수론 유형의 문제는 아이디어가 떠오르면 바로 풀고 아니면 못푸는게 참 안타깝다. 아이디어가 떠오르지 못하면 코드에 손도 못대는게 참 난처하다.